One-week intensive course on April 8 - 12, 2002:

An Introduction to Kolmogorov Complexity and Its Applications (1 cr)

Prof. Paul M. B. Vitányi
CWI & Universiteit van Amsterdam

Course description

"We are indeed in the information age and the scientific exploration of information and the laws that govern its behavior has taken center stage in the dramatic development of sciences. Kolmogorov complexity is a central concept and a powerful tool in the understanding of the quantitative nature of information and its processing and transmission. ... The basic concepts of Kolmogorov complexity should be understood by any technically educated person, and they should be studied by all computer scientists."

-- Juris Hartmanis, (Turing Award Winner 1993), NSF, Washington D.C.
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-Löf tests for randomness, Gödel'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.

About the lecturer

[Image of the lecturer]

Paul M.B. Vitányi received his Ph.D. from the Free University of Amsterdam (1978) and he holds positions at the national CWI Research Institute in Amsterdam and is professor of Computer Science at the University of Amsterdam. He serves on the editorial boards of Distributed Computing, Information Processing Letters, Theory of Computing Systems, Parallel Processing Letters, International journal of Foundations of Computer Science, Journal of Computer and Systems Sciences (guest editor), and elsewhere. He has worked on cellular automata, computational complexity, distributed and parallel computing, machine learning and prediction, physics of computation, Kolmogorov complexity, quantum computing. Together with Ming Li they pioneered applications of Kolmogorov complexity and co-authored ``An Introduction to Kolmogorov Complexity and its Applications,'' Springer-Verlag, New York, 1993 (2nd Edition 1997), parts of which have been translated into Chinese, Russian and Japanese.

Web page: http://www.cwi.nl/~paulv/

Details