CS 898: Applications of Kolmogorov complexity
Spring 2014

Home |

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

The course material will be mainly from the textbook, research papers, and the ppt lecture notes. The students will do a research project at the end of the term, and present it in class.

This course will focus on the applications of Kolmogorov complexity, rather than its theory. 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 cover the complete textbook, rather we will focus more on recent developments but we will focus on the applications, especially I wish to spend more time on new potential applications including natural language processing and compressive sensing.

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