CS 898: Kolmogorov complexity and its applications
Winter 2021

Home |

Ming Li Contact me by email mli@uwaterloo.ca
Course time and location:The official course time is Fridays 2:00-4:50pm. We will hold the first meeting at this slot on Jan. 15, 2pm EST, on zoom: zoom meeting id: 863 4846 7016. (There is no passcode) Regular meeting time for Q and A will be back to Fridays 2:00pm--whenever we are done, at the same zoom meeting id: 863 4846 7016, with no passcode. The students will view the recorded lectures online at their convenience (but please do this timely, taking the proper lectures for each week).
Office hours: Any time by email or phone 519-500-3026 (I am back to Waterloo now)
Textbook:Ming Li and Paul Vitanyi, An introduction to Kolmogorov complexity and its applications. 4th edition, Springer, 2019 (Other editions are ok too)

The course material will be mainly from the textbook, research papers, the ppt lecture notes and recorded zoom session presentations. The students will do three homeworks and a research project at the end of the term, and present it via zoom (recorded).

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, zero-shot learning. It is impossible to cover the complete textbook, rather we will focus more on recent developments but we will focus on the applications, especially I wish to explore potential applications of Kolmogorov complexity in deep learning and zero-shot learning.

Marking Scheme: Each student is expected to do three homeworks (20% each) and a final project and presentation in class (via zoom recording) which can be either theoretical or programming (40%).

Course announcements and lecture notes will appear on this page. You are responsible for reading it regularly.


(All exercise numbers refer to the 4th edition of the textbook unless otherwise stated) Please submit your assignments via email mli@uwaterloo.ca before the deadline.

Possible project topics:

Lectures (The videos will be uploaded gradually):


Maintained by Ming Li