Path: utzoo!attcan!utgpu!watmath!maytag!plragde
From: plragde@maytag.waterloo.edu (Prabhakar Ragde)
Newsgroups: ut.theory
Subject: course on Kolmogorov complexity at Waterloo
Message-ID: <486@maytag.waterloo.edu>
Date: 18 Sep 89 14:13:48 GMT
Reply-To: plragde@maytag.waterloo.edu (Prabhakar Ragde)
Distribution: ut
Organization: U. of Waterloo, Ontario
Lines: 139

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