CMSC 38512 Kolmogorov Complexity

Instructor

Janos Simon
165 Ryerson
2-3488
simon AT cs DOT uchicago DOT edu
Office Hours: by arrangement

Textbook

Ming Li and Paul Vitanyi: An Introduction to Kolmogorov Complexity and Its Applications
Third Edition, Springer Verlag, 2008
ISBN 987-0-387-49820-1

Course Overview

Theory of Kolmogorov Complexity and Applications in Theoretical Computer Science.
I will try to cover in the course
Definition and properties of Algorithmic Complexity C(x)
Algorithmic Prefix Complexity K(x)
Applications in Theoretical Computer Science (Incompressibility Method)
Topics to be defined (Applications to Learning, average-case complexity. Possibly, resouce-bounded variants.)

Material covered so far
Introduction -- Chapter 1, Sections 1.1, 1.8 (I assume you know most of 1.2-1.7)
Chapter 2, sections 2.1 and 2.2
Chapter 6. Sections 6.1,6.3, 6.6.1

Evaluation/Grading

There will be problem sets, and a take-home final. I will also give "do-exercises".
You should do them if you do not know how to do them. Typically, these are not graded.

Assignments and Handouts

Assignments are due in class the week after they were assigned.

Assignments given so far.

First Assignment. Due Tuesday, November 3.

http://people.cs.uchicago.edu/~simon/