Algorithmic Information Theory
For the basics of the course, we will follow sections 1, 2, 3
and 5 from in the notes from the older
offerings. We will have the following topics in the second half
of the course.
- Martingales over binary sequences
- The Ziv Lempel Algorithm (LZ78)
- Optimality properties of the Ziv Lempel Algorithm
- The Law of Large Numbers - Weak, Strong
- Normal numbers
Meeting Times
The meeting times are Monday and Wednesday: 5:10 to 6:25 pm
over the Zoom link which will be communicated over the course
id. The class will be in a synchronous mode. But the video will be
recorded and uploaded for later viewing.
Grading policy
The course will have 2 assignments and 2 exams, with the
following weightage:
Homeworks: 15 percent each
Midsem : 30 percent
Endsem : 40 percent
The TA is Prateek Vishnoi. His email id is pratvish.
Additional Notes
In addition to the Notes of Section 4 which deal with
martingales, the following gives an alternative approach to the
theory of constructive
martingales: Notes on Constructive
Martingales
Special Topics
- Normal Numbers and finite-state compression
- The Lempel-Ziv algorithm, universal (over finite-state)
compression.
- Applications of expander graphs and extractors to Algorithmic
Information Theory.
Additional References
-
Short Lists with Short Programs in Short Time - A Short Proof
by Marius Zimand.
- Fortune's Formula: The Untold Story of the Scientific Betting
System That Beat the Casinos and Wall Street, by William
Poundstone
Homeworks
- Homework 1 due the Friday before
Midsem week.
- Homework 2 due April 17 2019.