Kolmogorov complexity, Applications, MDL (course code MLIKC10)
Spring 2009

Paul Vitanyi CWI, Science Park 123, 1098XG (formerly, Kruislaan 413, 1098SJ) Amsterdam 5924124 paulv@cwi.nl
Course time:Thursday 4:00--7:00pm Euclides P0.15A (Vitanyi)
Wouter Koolen-Wijkstra CWI, Science Park 123, 1098XG (formerly, Kruislaan 413, 1098SJ) Amsterdam 5924086 wmkoolen@cwi.nl
Course time:Friday 1:00-- 3:00pm Euclides P.016 (Wouter Koolen-Wijkstra) instruction and treatment homework.
Office hours:Contact Wouter Koolen-Wijkstra .
Textbook:Ming Li and Paul Vitanyi, An introduction to Kolmogorov complexity and its applications. 3rd edition, Springer, 2008. The 3rd edition has a couple of hundred pages more that the 2nd edition, many corrections etc., and is about $20 cheaper than the 2nd edition on Amazon ($67,96). Book on Kolmogorov Complexity, the NEW 3rd edition of 2008.

The course material will be mainly from our textbook and papers that will be provided at this website. The students will make weekly homework, hand it in to the Kolmogorov complexity homework mailbox at the Euclides building by the next Wednesday afternoon 17:00 so that Wouter can treat the corrected homework at the following Friday sessions. There will be a mid-term written exam and a final exam.

This course 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 to bioinformatics and from document comparison to internet search, prefix complexity, universal distribution (Solomonoff-Levin), Solomonoff prediction, and minimum description length (MDL) hypothesis selection. 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 every week homework and mid-term and final exam. Maybe the exams will be replaced by a final project, which can be either theoretical or programming, which is presented in class. We will see what is feasible. Homework 30%, midterm and final exam or final project and presentation 60% (30% each), 10% class attendance (including guest lectures and student presentations) and participation in discussions.

Grading and Credits: Credits: 10EC. There will be a mid-term exam in early April, and a final exam in June. If the audience is capable and willing exams may be replaced by challenge tasks possibly executable by teams of two.

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


Note: The lecture notes are constantly being improved, so it is a good idea to download the most recent version before class. Since they are improved after class as well, the version a few days after class is even better. The description of homework and lectures is given both with regard to the 2nd edition of 1997 of the textbook and to the 3rd edition of 2008 of the textbook, leaving the info added to the 2nd edition.

Possible project topics:


No announcements.

Maintained by Paul Vitanyi. These lecture notes, power point presentations, and selection of papers, are developed in cooperation with Ming Li, David R. Cheriton School of Computer Science, University of Waterloo, Waterloo, Ontario N2L 3G1 Email: mli at uwaterloo dot ca.