First Course Handout for CS687 2022-23 II

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

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

6. The class covered a proof of van Lambalgen's Theorem. This proof is from the paper "Resource-bounded van Lambalgen's Theorems" by D. Chakravarthy, S. Nandakumar and H. Shukla, 2017, available at the publications page on my website.

7. Basics of Shannon Information Theory

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.