CS 898: Applications of Kolmogorov complexity Spring 2014 Home

   

Instructor:
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.

Assignments:

• Assignment 1. The assignment 1 contains the following problems from the book: 2.1.1[a], 2.1.2, 2.1.3, 2.1.5, 2.1.13, 2.2.5, 2.2.6, 2.2.8, and optional 2.3.4. The above pdf file is from John Hearns (Thanks John!) which might contain more problems that required). Due May 24, 2005 in class.
• Assignment 2. Do Exercises 2.4.2, 2.5.1, 2.5.2, 2.5.3, 2.7.5 from the text book, and prove the following statement: If a binary sequence x of length n has exactly n/2 0's, then x is not c-incompressible, for large enough n.
• Assignment 3. Problem 1: Use Kolmorogov complexity to prove that a 1 head 2-way DFA cannot accept L={w#w | w in {0,1}*}. Problem 2: Using Kolmorov complexity, obtain the average case lower bound for binary search. Problem 3: Using Kolmogorov complexity (directly, without using theorems from Chapter 6), prove that {0^n 1^m | m>n} is not regular. Problem 4. Do Excercise 6.8.5. Problem 5: Shaker sort compares each adjacent pair of items in a list in turn, swapping them if necessary, and alternately passes through the list from the beginning to the end then from the end to the beginning. It stops when a pass does no swaps. Using incompressibility argument, prove a tight average case lower bound for Shaker sort. Problem 6. Do Exercise 6.3.1, using Kolmogorov complexity. Problem 7. Do Exercise 6.3.2, using Kolmogorov complexity.

Possible project topics:

• Energy-time trade off for information processing (lecture 4). This is a theoretical research oriented project, related to Lecture 4.
• Alternative normalization of E(x,y) in Lecture 4.
• Experimental project. Explore google distance, as discussed in Lecture 5 notes.
• Google distance approach applied to protein-protein relationship. This is proposed by Brona Brejova. This is probably suitable for a bioinformatics student.
• History and comparative study of information distance metrics. (Talk to me, I will provide some papers.)
• Can you do an average-case analysis of Quicksort using Kolmogorov complexity (Open)?
• Improve the Shellsort average-case lower bound (Open). This is very difficult.
• Incompressibility method: find a problem in your own research, make an average case or lower bound analysis of your problem.
• Please do not hesitate to discuss with me on both finding and solving your project problems. Please let me know what you wish to work on. We generally do not allow two people working on the same project, unless it has some research component.

Lectures:

• Lecture 1. History, definition of Kolmogorov complexity, basics (Chapters 1 and 2). 1 week. Lecture 1 notes, ppt file
• Lecture 2: Randomness. Definitions and Martin-Lof tests (Sections 2.4, 2.5). 1 week. Lecture 2 notes, ppt file
• Lecture 3: Symmetry of Information (Section 2.8). 1 week. Lecture 3 notes, ppt file
• Lecture 4: Information Distance normalized information distance and applications. (Sections 8.2, 8.3, 8.4, 8.6 this paper, this paper, and this paper). 2-3 weeks. Lecture 4 notes, ppt file). 2 weeks.
• Lecture 5: The incompressibility method and its applications in average case analysis and lower bounds (Chapter 6) Lecture 5 notes, ppt file Additional lecture 5 notes by Tao Jiang, ppt file 2 weeks.
• Lecture 5.1: Lecture notes for June 28. The incompressibility method continued. Lecture 5.1 notes, ppt file Sorry about being late for this one. Please download before class if you see this. 1 week.
• Lecture 6: Prefix Kolmogorov complexity (Chapter 3) Lecture 6 notes, ppt file 1 week.
• Lecture 7: Inductive Inference (Chapter 5) Lecture 7 notes, ppt file 1 week.
• Lecture 8: Kolmogorov complexity and the nature (Chapter 8) Lecture 8 notes, ppt file 1/2 week.
• Lecture 9: Resource bounded Kolmogorov complexity and computational complexity (Chapter 7). Lecture 9 notes, ppt file For those who are interested in reading more, you can read this Lance Fortnow notes). 1 week.
• Student presentations: 2 weeks (1/2 hour each student).

Announcements:

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).