Search the Dagstuhl Website
Looking for information on the websites of the individual seminars? - Then please:
Not found what you are looking for? - Some of our services have separate websites, each with its own search option. Please check the following list:
Schloss Dagstuhl - LZI - Logo
Schloss Dagstuhl Services
Within this website:
External resources:
  • DOOR (for registering your stay at Dagstuhl)
  • DOSA (for proposing future Dagstuhl Seminars or Dagstuhl Perspectives Workshops)
Within this website:
External resources:
Within this website:
External resources:
  • the dblp Computer Science Bibliography

Dagstuhl Seminar 06051

Kolmogorov Complexity and Applications

( Jan 29 – Feb 03, 2006 )

(Click in the middle of the image to enlarge)

Please use the following short url to reference this page:



The Kolmogorov complexity of an object is the minimal number of bits required to effectively describe the object. This complexity measure 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 was meant to be cross-disciplinary and to connect 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. These topics were covered by 38 technical talks; in addition there were 5 historical talks and a subsequent panel discussion on the early history of Kolmogorov complexity. The seminar was attended by 50 participants, including a large number of leading researchers from the fields listed above. The seminar enabled the participating researchers to assess the state of the art and to inform themselves about new developments, the interdisciplinary character of the seminar helped to forge cohesion in the research community.

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. Hirschfeldt, 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).

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. The current trends mentioned above have been very well represented by participants and talks of the seminar.

  • Eric Allender (Rutgers University - Piscataway, US) [dblp]
  • Klaus Ambos-Spies (Universität Heidelberg, DE) [dblp]
  • Luis Filipe Coelho Antunes (University of Porto, PT)
  • Veronica Becher (University of Buenos Aires, AR) [dblp]
  • Cristian Calude (University of Auckland, NZ)
  • Alexey Chernov (IDSIA - Manno, CH)
  • Steven de Rooij (CWI - Amsterdam, NL)
  • Santiago Figueira (University of Buenos Aires, AR)
  • Serge Grigorieff (University Paris-Diderot, FR) [dblp]
  • Peter Grünwald (CWI - Amsterdam, NL)
  • Nick Hay (University of Auckland, NZ)
  • Denis R. Hirschfeldt (University of Chicago, US) [dblp]
  • John Hitchcock (University of Wyoming - Laramie, US)
  • Günter Hotz (Universität des Saarlandes, DE) [dblp]
  • Marcus Hutter (IDSIA - Manno, CH) [dblp]
  • Yuri Kalnishkan (Royal Holloway University of London, GB)
  • Björn Kjos-Hanssen (University of Connecticut - Storrs, US) [dblp]
  • Wouter Koolen-Wijkstra (CWI - Amsterdam, NL)
  • Michal Koucký (Czech Academy of Sciences - Prague, CZ) [dblp]
  • Antonin Kucera (Charles University - Prague, CZ)
  • Shane Legg (IDSIA - Manno, CH)
  • Elvira Mayordomo (University of Zaragoza, ES) [dblp]
  • Wolfgang Merkle (Universität Heidelberg, DE) [dblp]
  • Jochen Messner (Universität Ulm, DE) [dblp]
  • Joseph S. Miller (University of Connecticut - Storrs, US) [dblp]
  • Philippe Moser (University of Zaragoza, ES)
  • Andrej A. Muchnik (INT - Moscow, RU)
  • Jan Poland (Hokkaido Univ. - Sapporo, JP)
  • Jan Reimann (Universität Heidelberg, DE) [dblp]
  • Rüdiger Reischuk (Universität Lübeck, DE) [dblp]
  • Andrei Romashchenko (IITP - Moscow, RU)
  • Andrei Rumyantsev (Moscow State University, RU)
  • Boris Ryabko (Russian Academy of Sc. - Novosibirsk, RU)
  • Daniil Ryabko (IDSIA - Manno, CH)
  • Jürgen Schmidhuber (IDSIA - Manno, CH) [dblp]
  • Claus Peter Schnorr (Universität Frankfurt, DE) [dblp]
  • Uwe Schöning (Universität Ulm, DE) [dblp]
  • Rainer Schuler (Universität Ulm, DE)
  • Alexander Shen (IITP - Moscow, RU) [dblp]
  • Theodore A. Slaman (University of California - Berkeley, US) [dblp]
  • Ludwig Staiger (Universität Halle-Wittenberg, DE)
  • Sebastiaan A. Terwijn (TU Wien, AT) [dblp]
  • Leen Torenvliet (University of Amsterdam, NL)
  • John Tromp (CWI - Amsterdam, NL)
  • Nikolay K. Vereshchagin (Moscow State University, RU) [dblp]
  • Paul M. B. Vitanyi (CWI - Amsterdam, NL)
  • Vladimir Viyugin (IITP - Moscow, RU)
  • Vladimir Vovk (Royal Holloway University of London, GB)
  • Marius Zimand (Towson University, US)

Related Seminars
  • Dagstuhl Seminar 03181: Centennial Seminar on Kolmogorov Complexity and Applications (2003-04-27 - 2003-05-02) (Details)

  • artificial intelligence / robotics

  • information theory
  • Kolmogorov complexity
  • effective randomness
  • algorithmic probability
  • recursion theory
  • computational complexity
  • machine learning and statistics
  • pattern recognition
  • data mining
  • and knowledge discovery.