https://www.dagstuhl.de/06051

January 29 – February 3 , 2006, Dagstuhl Seminar 06051

Kolmogorov Complexity and Applications

Organizers

Marcus Hutter (IDSIA – Manno, CH)
Wolfgang Merkle (Universität Heidelberg, DE)
Paul M. B. Vitanyi (CWI – Amsterdam, NL)

For support, please contact

Dagstuhl Service Team

Documents

Dagstuhl Seminar Proceedings DROPS
List of Participants
Dagstuhl's Impact: Documents available

Summary

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.

Related Dagstuhl Seminar

Classification

  • Artificial Intelligence / Robotics

Keywords

  • Information theory
  • Kolmogorov complexity
  • Effective randomness
  • Algorithmic probability
  • Recursion theory
  • Computational complexity
  • Machine learning and statistics
  • Pattern recognition
  • Data mining
  • And knowledge discovery.

Documentation

In the series Dagstuhl Reports each Dagstuhl Seminar and Dagstuhl Perspectives Workshop is documented. The seminar organizers, in cooperation with the collector, prepare a report that includes contributions from the participants' talks together with a summary of the seminar.

 

Download overview leaflet (PDF).

Publications

Furthermore, a comprehensive peer-reviewed collection of research papers can be published in the series Dagstuhl Follow-Ups.

Dagstuhl's Impact

Please inform us when a publication was published as a result from your seminar. These publications are listed in the category Dagstuhl's Impact and are presented on a special shelf on the ground floor of the library.

NSF young researcher support