Lecture 2

Basic properties of K-complexity. Using K-complexity to analyze prime numbers.

Scribe Notes by Michael Wurtz

Lecture 1

What is randomness? The basic definitions and properties of Kolmogorov complexity.

Kolmogorov Complexity by Lance Fortnow. Notes from a 2000 New Zealand Summer School.


Scribe Notes by Darrell Hoy

Course Information

EECS 395/495-0-20: Kolmogorov Complexity

Spring 2011

Lecturer: Lance Fortnow

Lectures: MWF 9:00-9:50 in Tech LG68

Description:

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.