CS 898: Applications of Kolmogorov complexity
Spring 2014

Home | Fun readings

Ming Li DC 3355, x84659 mli@uwaterloo.ca
Course time:Wednesdays 1:00--3:50pm DC 2568
Office hours:Wed 4:00-6:00pm or just drop by my office DC 3355 any time.
Textbook:Ming Li and Paul Vitanyi, An introduction to Kolmogorov complexity and its applications. 3rd edition, Springer, 2008

This course is a graduate seminar course. The course material will be mainly from our textbook and papers that will be provided at this website. The students will perform a small research project at the end of the term, and present them in class.

Note that this course is not a bioinformatics course. It is a general course on Kolmogorov complexity and many of its applications. The goal of this course is to teach you how to use this tool in your own research, rather than doing research in the theory of Kolmogorov complexity.

Possible topics are: plain Kolmogorov complexity, randomness, prefix Kolmogorov complexity, incompressibility method, information distance, applications in various fields ranging from average-case analysis of algorithms to bioinformatics and from document comparison to google search. We will not be able to cover the complete textbook, rather we will focus more on recent developments and especially the recent exciting applications of Kolmogorov complexity.

Marking Scheme: Each student is expected to do three homeworks and a final project, which can be either theoretical or programming, and present the project in class. Three homeworks 15% each, in class presentation 20%, and final project 35%.

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


Possible project topics:


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


There is no class on June 21. I will be at the CPM conference in Korea. See you on June 28.

I have finished unifying (June 15) the notation of K and C in all lecture notes (Lectures 1-7).

On June 28, we will do one more class on incompressibility method. Then on July 5th, we do prefix complexity and inductive inference (Lecture notes 6 and 7).

Maintained by Ming Li