CS 898: Applications of Kolmogorov complexity
Spring 2014
Home 

Home
 Fun readings
Instructor: 
Ming
Li 
DC 3355, x84659 
mli@uwaterloo.ca 
Course time:  Wednesdays 1:003:50pm DC 2568 
Office hours:  Wed 4:006: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
averagecase 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 cincompressible, for large
enough n.

Assignment 3. Problem 1: Use Kolmorogov complexity
to prove that a 1 head 2way 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:

Energytime 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 proteinprotein 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 averagecase analysis of Quicksort using Kolmogorov
complexity (Open)?

Improve the Shellsort averagecase 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:
Note: The lecture notes in powerpoint will gradually appear below.
The lecture notes are constantly being improved, so it is a good idea
to download the most recent version before class.

Lecture 1. History, definition of Kolmogorov complexity, basics
(Chapters 1 and 2). 1 week.
Lecture 1 notes, ppt file

Lecture 2: Randomness. Definitions and MartinLof 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). 23 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 17).
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).
Maintained by Ming Li