CS 898: Kolmogorov complexity and its applications
Winter 2023

Home | cs.uwaterloo.ca/~mli/

Ming Li Contact me by email mli@uwaterloo.ca
Course time and location:The official course time is Fridays 9:00-11:50am. We will hold the first class during this time on Jan. 13, 9am EST, on zoom. Our zoom meeting id will always be: 863 4846 7016. (There is no passcode) All the lectures have been recorded. The students will view the recorded lectures online at their convenience before the lecture time. Then at the the class time, I will go thru the ppt, and explain the key points and answer questions.
Office hours: Any time by email, and we can hold separate zoom sessions.
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.

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. This term we will focus on how Kolmogorov complexity can be used in deep learning and help to resolve problems such as few shot learning.

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 few 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 discuss in depth on Kolmogorov complexity applications to few 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.

Project topics:

Other possible project topics:


Student Presentations (Starting April 10, 9am):


Maintained by Ming Li