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.
- 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.