plragde@maytag.waterloo.edu (Prabhakar Ragde) (09/18/89)
A course on Kolmogorov complexity and its applications is being taught this
term at Waterloo by Ming Li (formerly at York). Together with Vitanyi, he
is writing a textbook on the subject, and a preliminary draft will be used
in this course. It is a graduate research course, and people from Toronto
are welcome to attend. Today's lecture (which you will probably miss) will
be introductory, and you can probably catch up using the textbook and with
the aid of those of us who are attending. --PR
---------------------------------------------------------
_A_n_y_o_n_e _w_h_o _c_o_n_s_i_d_e_r_s _a_r_i_t_h_m_e_t_i_c_a_l _m_e_t_h_o_d_s _o_f _p_r_o_d_u_c_i_n_g _r_a_n_-
_d_o_m _d_i_g_i_t_s _i_s, _o_f _c_o_u_r_s_e, _i_n _a _s_t_a_t_e _o_f _s_i_n.
--- John Von
Neuman (1951)
CS 767: Introduction to Kolmogorov Complexity and Its Applications
Mondays 3:30-5:30pm (Starting September 18, 1989), DC3307
Instructor: Ming Li
Office Hours: 24 hours a day, 7 days a week, DC2339, 888-
4659
Course Contents: I will basically follow the book* (Li and
Vitanyi: "An introduction to Kolmogorov complexity and it
applications"), skipping the preliminary part of Chapter 1.
The following are the major topics (although I doubt if we
have time to cover all in detail).
(a) History and roots of Kolmogorov complexity (Chapter
1.4), and some Theory of Algorithms, in particular the
notions of recursive and enumerable (or semi-
computable) functions.
(b) Plain Kolmogorov complexity _C: Invariance theorem; Sym-
metry of information; Incompressibility; Randomness of
finite and infinite sequences; Martin-Lof tests for
randomness; Behavior and Algorithmic properties of _C
viewed as an integer function; Algorithmic Information
Theory. Applications to lower bound proofs, combina-
torics, formal language theory, parallel computation,
Godel's Theorem, etc.
(c) Prefix Kolmogorov complexity _K: Prefix codes; Kraft
inequality; Invariance theorem; Incompressibility and
randomness; Information-theoretic identities. Algo-
rithmic Probability Theory: Discrete semi-measures and
Solomonoff-Levin distribution; Monotonic Algorithms and
Universal A priori probability (continuous version of
Solomonoff-Levin distribution); Applications to induc-
tive reasoning and machine learning (Occam's Razor
principle, Gold paradigm, Valiant's Learning model,
Rissanen's Minimum Description Length Principle,
Jaynes' Maximum Entropy principle, completeness results
for learning simple concepts under simple distribu-
tions); Applications to probability theory: tests for
randomness with respect to computable distributions,
Martingales or How to Gamble.
(d) Resource bounded Kolmogorov complexity: Theory;
Language compression, ranking; Applications to computa-
tional complexity.
September 18, 1989
- 2 -
Course Requirements and Grading Scheme: There will be 2
assignments and 1 term paper (of about 10-20 pages) for
those who are taking the course for credits. By the end of
the term, you will present your paper in class (time length
to be decided -- but less than an hour in any case). 50%
marks depends on class participation. 20% marks for 2
assignments and 30% marks for the term paper. Please come to
me to arrange a topic for the term paper as early as possi-
ble.
_________________________
* About the book: This is a preliminary draft. Please
do not distribute because it may contain: technical er-
rors, typos, bad English grammar, inconsistent nota-
tions, personal remarks, irresponsible comments, email
letters from third parties, and especially many ques-
tion marks. All suggestions are gratefully welcomed.
September 18, 1989