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.

  1. Martingales over binary sequences
  2. The Ziv Lempel Algorithm (LZ78)
  3. Optimality properties of the Ziv Lempel Algorithm
  4. The Law of Large Numbers - Weak, Strong
  5. 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

  1. Normal Numbers and finite-state compression
  2. The Lempel-Ziv algorithm, universal (over finite-state) compression.
  3. Applications of expander graphs and extractors to Algorithmic Information Theory.

Additional References

  1. Short Lists with Short Programs in Short Time - A Short Proof by Marius Zimand.
  2. Fortune's Formula: The Untold Story of the Scientific Betting System That Beat the Casinos and Wall Street, by William Poundstone

Homeworks

  1. Homework 1 due the Friday before Midsem week.
  2. Homework 2 due April 17 2019.