|
![]() |
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
![]()
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
30.1.2006
Monday
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 31.1.2006
Tuesday
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] 1.2.2006
Wednesday
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] 2.2.2006
Thursday
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] 3.2.2006
Friday
Mixed
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
![]()
Audience
![]()
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