Dagstuhl Seminar 06051

Kolmogorov Complexity and Applications

29 Jan. - 3 Feb. 2006

Organised by:
Marcus Hutter
Wolfgang Merkle 
Paul Vitanyi
IDSIA, Lugano, CH
Univ. Heidelberg, DE
CWI, Amsterdam, NL
Dagstuhl Schloss


Computational complexity has been the subject of quite many seminars in the past, especially the time or storage space required to perform a computation. Kolmogorov complexity is a related complexity measure: the minimal number of bits required to effectively describe an object. This resource becomes ever more important in the practical setting because it gives the ultimate limits to what is achievable by data compression (a central application area) and in the theoretical setting in an ever more diverse number of areas. Shortest description length is a central theme that is basic to the pursuit of science, and goes back to the principle known as Occam's razor, one version of which amounts to the rule that if presented with a choice between indifferent alternatives, then one ought to select the simplest one. Unconsciously or explicitly, informal applications of this principle in science and mathematics abound.

Kolmogorov complexity (also known as algorithmic information theory) is widely applied in computer science and a plethora of other scientific disciplines. The seminar will assess the state of the art and serves to inform the invited researchers of new developments and to forge cohesion in the research community. The seminar is cross-disciplinary and connects through the common technique of Kolmogorov complexity the areas information theory, individual randomness, algorithmic probability, recursion theory, computational complexity, machine learning and statistics, pattern recognition, data mining, and knowledge discovery.

In 2005, the field of Kolmogorov complexity is vigorously alive, with new developments consisting of books in the making or just published about (i) the "renaissance" of recursion theory focussed on the analysis of individual randomness in terms of Kolmogorov complexity and related formalisms (R. Downey and D. Hirschfeld, Algorithmic Randomness and Complexity, Springer, to appear); (ii) new trends in statistical inference and learning theory, artificial intelligence, based on compression (M. Hutter, Universal Artificial Intelligence: Sequential Decisions Based on Algorithmic Probability, EATCS Monographs, Springer 2004); (iii) pattern recognition, clustering and classification based on compression, Kolmogorov's structure function and algorithmic sufficient statistic, and distortion theory MDL and relations between information theory and Kolmogorov complexity (P. Vitanyi, Algorithmic Entropy, Algorithmic Distortion Theory, Springer, in preparation). In this connection, note the recent media splash about automatic meaning discovery using Google (see for example D. Graham-Rowe, A search for meaning, New Scientist, 29 January 2005, p.21). There is (iv) the area of the incompressibility method based on Kolmogorov complexity that keeps resolving decade-long (sometimes half-century) open problems in mathematics and computer science.

All these different directions, spawned and grounded on Kolmogorov complexity theory, will come together in the Dagstuhl seminar to share insight and increase synergy. A long list of significant open problems can be found in the cited books; in fact the different strains of scientific exploration in the field moves fast and wide.

Participants' Photo

Participants of the Dagstuhl Kolmogorov Seminar Wolfgang Merkle Klaus Ambos-Spies Jochen Messner Philippe Moser Rüdiger Reischuk Sebastiaan Terwijn Marius Zimand Leen Torenvliet Jan Reimann Santiago Figueira Wouter Koolen-Wijkstra Rainer Schuler Luis Antunes Marcus Hutter Nick Hay John Tromp Elvira Mayordomo Alexey Chernov Nikolai Vereshchagin Andrei Rumyantsev Jan Poland Vladimir V'yugin Alexander Shen Volodya Vovk Veronica Becher Shane Legg Andrej Romashchenko Claus Schnorr Joseph Miller Eric Allender Steven de Rooij Yuri Kalnishkan Denis Hirschfeldt Michal Koucky Paul Vitanyi John Hitchcock Theodore Slaman Cristian Calude Bjørn Kjos-Hanssen Ludwig Staiger Daniil Ryabko Boris Ryabko
Hover over a person to see their name, click to see a picture of them.

Others in attendance: Günter Hotz, Andrej A. Muchnik, Jürgen Schmidhuber, Peter Grünwald, Serge Grigorieff.

Panel discussion: History of Algorithmic Randomness & Complexity

Early history of probability and randomness

Paul Vitanyi

Complete audio 4MB mp3
Video extract 93MB mpg
Personal account of the development of Kolmogorov complexity

Claus Schnorr

Complete audio 7MB mp3
Mapping out the convoluted history of the field

Alexander Shen

Complete audio 9MB mp3
Video extract 25MB mpg
Some stories about the development of algorithmic information theory

Cristian Calude

Complete audio 6MB mp3
Video extract 27MB mpg
What is randomness and does it exist in physics?

Günter Hotz

Complete audio 5MB mp3
Video extract 21MB mpg

Partial reconstruction of the history at the end of the day

Schedule of Sessions and Talks



Recursion Theory and Algorithmic Randomness

9:15 - 10:00 Denis Hirschfeldt Introduction to Randomness, Recursion Theory Kolmogorov Complexity   [slides]
10:30 - 10:50 Andrej Romanshchenko   On Stability of Kolmogorov Properties under Relativization   [abstract]   [slides]
11:00 - 11:20 John Tromp Binary Lambda-Calculus and Combinatory Logic   [abstract]

Information Theory

14:00 - 14:45 Nikolai Vereshchagin Algorithmic Rate Distortion Theory   [abstract]   [paper]
15:00 - 15:20 Steven de Rooij Algorithmic Rate Distortion in Practice
16:00 - 16:20 Alexander Shen Multisource Information Theory and Combinatorics   [extended abstract]
16:30 - 16:50 Boris Ryabko Kolmogorov Complexity and Mathematical Statistics
17:00 - 17:30 Paul Vitanyi Automatic Meaning Discovery using Google   [paper]
17:35 - 17:50 Paul Vitanyi Shannon Information Kolmogorov Complexity



Universal Induction

9:10 - 9:40 Shane Legg Is there an Elegant Theory of Prediction?   [slides]
9:45 - 10:10 Vladimir V'yugin On Impossibility of Sequential Algorithmic Forecasting
10:45 - 11:10 Yuri Kalnishkan Predictive Complexity Overview
11:15 - 11:40 Alexey Chernov Complexity Monotone in Conditions   [abstract]   [slides]
11:45 - 12:10 Marcus Hutter On the Convergence of (Non)Universal Semimeasures on Martin-Löf Random Sequences   [abstract]   [slides]

Learning Theory

13:45 - 14:25 Jürgen Schmidhuber Proof-Based General Search Algorithms and Gödel-Machines [slides]
14:30 - 14:55 Peter Grünwald Inconsistency Misspecification
15:00 - 15:25 Daniil Ryabko Learning in Reactive Environments with Arbitrary Dependence   [slides]

Prediction with Expert Advice

16:00 - 16:25 Andrej Muchnik Optimal Aggregation of Expert Advices
16:30 - 16:55 Vladimir Vovk A Dual Approach to Universal Prediction   [abstract]   [slides]
17:00 - 17:25 Jan Poland New Results in (Non-)Universal Induction   [abstract]   [slides]   [paper]



Recursion Theory

9:10 - 9:40 Theodore Slaman Relative n-Randomness for Continuous Measures
9:45 - 10:10 Sebastiaan Terwijn On the Difference between Martin-Löf Randomness and Schnorr-Randomness   [abstract]
10:45 - 11:10 John Hitchcock Extracting Kolmogorov Complexity   [abstract]
11:15 - 11:40 Andrei Rumyantsev Forbidden Substrings and Subsequences   [abstract]   [slides]   [paper]
11:45 - 12:10 Luis Antunes Time-Bounded Universal Distributions   [abstract]



Complexity Theory

9:10 - 9:40 Eric Allender Open Questions in Kolmogorov Complexity and Computational Complexity   [abstract]
9:45 - 10:10 Cristian Calude Partial Randomness Zeta Functions   [abstract]   [slides]
10:45 - 11:10 Rüdiger Reischuk On String Compression by Context-Free Grammars
11:15 - 11:40 Michal Koucky High-Entropy Random Selection Protocols
11:45 - 12:10 Marius Zimad On Building Extractors from P.R. Generators   [slides]   [paper]

Recursion Theory

15:30 - 15:55 Veronica Becher Turing's Unpublished Algorithm for Normal Numbers
16:00 - 16:25 Ludwig Staiger Self-Similar Sets, Dimensions and Kolmogorov Complexity   [abstract]
16:30 - 16:55 Bjørn Kjos-Hanssen Eventually Different Functions
17:00 - 17:25 Serge Grigorieff From Index Sets to Randomness
17:30 - 18:00 Santiago Figueira Randomness and Halting Probabilities   [slides]




10:45 - 11:05 Joseph Miller Contrasting Plain and Prefix Complexity   [slides]
11:05 - 11:25 Nick Hay On the Accuracy of Universal Prediction   [slides]
11:25 - 11:45 Elvira Mayordomo The Analyst Traveling Salesman Problem   [abstract]   [slides]

Extra Pictures...

Dagstuhl Schloss in the fog

Frost on the windows


Group walk

Brightest shirt

Most graceful pose

Further Links

Photo credits: Yuri Kalnishkan, Rüdiger Reischuk, Marcus Hutter
For corrections etc. to this page email: marcus@idsia.ch or shane@idsia.ch