Algorithmic Information Theory
In the initial part of the course, we will follow the notes from
offering. We will have the following topics in the second half
of the course.
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
- Normal Numbers and finite-state compression
- The Lempel-Ziv algorithm, universal (over finite-state)
- Applications of expander graphs and extractors to Algorithmic
Lists with Short Programs in Short Time - A Short Proof by
- Homework 1 due the Friday before
- Homework 2 due April 17 2019.