Algorithmic Information Theory

Old notes are available at the the 2010 website. In the present offering, we will replace the second half of the course with the following topics, which are active areas of research:

  1. Short lists containing short programs in short time!, a recent work by Shen, Zimand et. al. from 2013, a connection between extractors and Kolmogorov Complexity, which (in my view) is the most fundamental result about Kolmogorov Complexity in about 40 years.
  2. Normal Numbers, which can be viewed as a very weak notion of randomness. Fundamental open questions are whether well-known transcendentals like π, e, etc. are normal, and whether there is any algebraic irrational which is normal.

    In the course, we show the following results - Pillai's equivalent characterization of normality using simple normality, the equivalence between finite-state incompressibility and normality, and the proof that a Champernowne-like sequence is finite-state incompressible, hence normal. (This utilizes a combinatorial insight inherent in Lempel and Ziv's 1978 paper on universal compression, and has not appeared explicitly anywhere.) [Notes]

Homework

  1. Homework 1, due March 1

References