CS 860: Kolmogorov complexity and its applications
Winter 2010

Home | Fun readings

Ming Li DC 3355, x84659 mli@uwaterloo.ca
Course time:Mondays 3:30-6:20pm
Office hours:Mondays 1-3pm
Textbook:Ming Li and Paul Vitanyi, An introduction to Kolmogorov complexity and its applications. 2n edition or 3rd edition, Springer, 2008

The course material will be mainly from our textbook, the ppt files, and papers that will be provided at this website. The students will do a research project at the end of the term, and present it in class.

Note that this course is not a bioinformatics course. It is a general course on Kolmogorov complexity and many of its applications. Kolmogorov complexity is a modern theory of information and randomness. The goal of this course is to teach the students the basic concepts of Kolmogorov complexity and how to use this tool in their own research.

Topics include: plain Kolmogorov complexity, randomness, prefix Kolmogorov complexity, incompressibility method, information distance, applications in various fields ranging from average-case analysis of algorithms, Lovasz Local Lemma, to bioinformatics; and from document comparison to internet search. We will not be able to cover the complete textbook, rather we will focus more on recent developments and especially on applications of Kolmogorov complexity.

Marking Scheme: Each student is expected to do three homeworks (20% each) and a final project and presentation in class (35%), which can be either theoretical or programming, and 5% class attendance and participation in discussions.

Course announcements and lecture notes will appear on this page. You are responsible for reading it (and downloading the lecture notes before classes) regularly.


(All exercise numbers refer to both the 2nd edition and 3rd edition of the textbook unless otherwise stated)

Possible project topics:


Note: The lecture notes are constantly being improved, so it is a good idea to download the most recent version before class.


Maintained by Ming Li