Algorithmic Information Theory

In the initial part of the course, we will follow the notes from the 2010 offering. We will have the following topics in the second half of the course.

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.

References

1. Short Lists with Short Programs in Short Time - A Short Proof by Marius Zimand.

Homeworks

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