First Course Handout for CS687 2023-24 II

The first course handout for the course can be obtained here.

The initial part of the course will focus on randomness of finite strings.

The initial lectures [8 lectures] will cover some of the basic techniques from set theory and computability theory needed for the course.

The course covers the motivations and basics of algorithmic information theory, namely, the notions of

1. Plain Kolmogorov Complexity [3 lectures]
2. Self-delimiting Kolmogorov Complexity [7 lectures]

Further, we will show that incompressible objects contain many properties which we expect from random objects. [4 lectures]

We will introduce some basic inequalities from classical information theory. [3 lectures]

The second half of the course will focus on the randomness of infinite objects. We will introduce the notion of Martin-Lof randomness using constructive measure [5 lectures] and cover the important properties of symmetry of relative randomness, i.e. van Lambalgen Theorem [5 lectures] and the Kucera-Gacs theorem [5 lectures].

In two lectures, we will give a brief overview of a currently emerging area of computational complexity theory, namely, meta-complexity. This is the study of problems which themselves describe their computational complexity. We will look at the intimate connections with Kolmogorov complexity.

1. Homeworks - 2 (weightage 2x15 = 30 percent)
2. Midsem - 30 percent
3. Endsem - 40 percent.

The lecture schedule is available as a text file. (Due to a severe cold wave in January, the class schedule was modified.)

1. Set theoretic and Computability Theoretic Preliminaries
2. Plain Kolmogorov Complexity
3. Self-delimiting Kolmogorov Complexity
4. Applications to probability theory
5. Martin-Löf randomness and properties of ML-randoms: van Lambalgen theorem and the Kučera-Gàcs theorem

Lecture notes will be provided. The following textbooks may be referred.

1. Li, Vitanyi. An Introduction to Kolmogorov Complexity and its Applications, 4th Edition, Springer, 2019.

1. Downey, Hirschfeldt. Algorithmic Randomness and Complexity, Springer, 2010.
2. Nies, Computability and Randomness, Oxford, 2009.
3. Shen, Uspensky, Vereschagin, "Kolmogorov Complexity and Algorithmic Randomness", AMS, 2017.