←

Algorithmic Information Theory

Directed Reading Program, Fall 2026

Algorithmic information theory (sometimes called Kolmogorov complexity theory) is the study of how much “information” lies in a given object (e.g. the constant pi, or a photograph.) It is a broad, interdisciplinary subject, in the locus of theoretical computer science, information theory, statistics, probability theory, and artificial intelligence.

We will have a narrower focus: following Li and Vitányi’s “An Introduction to Kolmogorov Complexity Theory and Its Applications”, we begin with an introduction to the elementary information theory developed by Shannon in 1948. Afterwards, we will direct our aim to developing the mathematics of algorithmic complexity theory: under differing frameworks, what is the answer to the question “How do we effectively describe objects?”.

We will conclude with some applications of the theory to problems in physics and computation according to student interest; examples include reversible computing, coding theory, thermodynamics, and compression.

(more information to come!)