Title: An Introduction to Kolmogorov Complexity and It's Applications
Time: April 26-29, 2004
Location: Room C454, Department of Computer Science, University of Helsinki, Teollisuuskatu 23
Schedule: Lectures each day from 9-12 and practice sessions in the afternoons 12-14.
All registered students have been accepted.
Grading: Active participation to all events of the course is required.
We treat the central ideas and their applications of Kolmogorov complexity---a modern notion of randomness dealing with the quantity of information in individual objects. Kolmogorov complexity is known variously as 'algorithmic information', 'algorithmic entropy', 'Kolmogorov-Chaitin complexity', 'descriptional complexity', 'shortest program length', 'algorithmic randomness', and others. We give an introductory treatment of the subject with a selection from a wide range of illustrative applications. Such applications include randomness of individual finite objects or infinite sequences, Martin-Loef tests for randomness, Goedel's incompleteness result, information theory of individual objects, universal probability, general inductive reasoning, inductive inference, prediction, mistake bounds, computational learning theory, inference in statistics, the incompressibility method, combinatorics, time and space complexity of computations, average case analysis of algorithms such as HEAPSORT, SHELLSORT, language recognition, string matching, formal language and automata theory, Turing machine complexity, lower bound proof techniques, probability theory, structural complexity theory, oracles, logical depth, universal optimal search, physics and computation, dissipationless reversible computing, information distance and picture similarity, bioinformatics, linguistics, cognitive psychology, thermodynamics of computing, statistical thermodynamics and Boltzmann entropy.
Special attention will be given to learning on-line handwritten characters (in one person's handwriting), clustering by compression, and nonprobabilistic statistics (a la Kolmogorov) and its relation to Shannon's rate-distortion theory. See the papers on http://homepages.cwi.nl/~paulv/kolmcompl.html, and especially:
- Q. Gao, M. Li and P.M.B. Vitanyi, Applying MDL to learning best model granularity, Artificial Intelligence, 121:1-2(2000), 1--29.
- R. Cilibrasi, P.M.B. Vitanyi, Clustering by compression, CWI manuscript 2003, Submitted.
- N. Vereshchagin and P. Vitanyi, Kolmogorov's Structure Functions with an Application to the Foundations of Model Selection, Proc. 47th IEEE Symp. Found. Comput. Sci. (FOCS'02), 2002, 751-760.
This series of talks is based on the (text)book by Ming Li and Paul Vitanyi, An Introduction to Kolmogorov Complexity and Its Applications, Springer-Verlag, New York, 2nd Edition, 1997. Outline on web page: http://www.cwi.nl/~paulv/kolmogorov.html
Articles in the popular press (New Scientist and others) see http://homepages.cwi.nl/~paulv/pop.html
A short syllabus by Alexander Shen can be found on the Kolmogorov Complexity webpage http://www.idsia.ch/~marcus/kolmo.htm or http://www.csd.uu.se/~vorobyov/Courses/KC/2000/