EECS 395/495-0-20: Kolmogorov Complexity
This course will study the Kolmogorov complexity of finite strings which measures the information content (or randomness) of a string by the size of the smallest program that generates it. This simple idea has a surprisingly deep theory with many exciting applications to logic and computer science. We cover the basic relationships of Kolmogorov complexity, applications with an emphasis in connections with computational complexity. Topics include: Basic Properties of the Kolmogorov function, Symmetry of Information, The Incompressibility Method, Resource-Bounded complexity, and applications to circuit complexity and randomized constructions.
This course is designed for graduate students or advanced undergraduates. We will assume familiarity with mathematical proofs but no previous knowledge of Turing machines or computational complexity.
Textbook: An Introduction to Kolmogorov Complexity and Its Applications by Ming Li and Paul Vitanyi.
This course is designed for graduate students or advanced undergraduates. We will assume familiarity with mathematical proofs but no previous knowledge of Turing machines or computational complexity.
Textbook: An Introduction to Kolmogorov Complexity and Its Applications by Ming Li and Paul Vitanyi.
