http://www.dagstuhl.de/03181

27. April – 02. Mai 2003, Dagstuhl Seminar 03181

Centennial Seminar on Kolmogorov Complexity and Applications

Organisatoren

Bruno Durand (University of Marseille, FR)
Leonid A. Levin (Boston University, US)
Wolfgang Merkle (Universität Heidelberg, DE)
Alexander Shen (IITP – Moscow, RU)
Paul M. B. Vitanyi (CWI – Amsterdam, NL)


Auskunft zu diesem Dagstuhl Seminar erteilt

Dagstuhl Service Team

Dokumente

Teilnehmerliste

Public Outreach

Algorithmic information theory (Kolmogorov complexity theory) measures the amount of information in a given finite object (bit string, file, message etc.) and formalizes the distinction between highly compressible objects that contain little information (regular objects) and incompressible objects with high information content (random objects). This idea was put forward in 1960's by several researchers, including the famous mathematician, Andrei Nikolaevich Kolmogorov, and led to a fruitful developments. The seminar celebrating 100th birthday anniversary of Kolmogorov, tried to gather the most active people in the field, including some disciples of Kolmogorov, for discussion.

Scientific Highlights

Several active fields of research were covered in the talks:

Relations between computational complexity and descriptional complexity. The idea of taking into account the computation time (needed for decompression) was clear already in 1960's. However, only recently this connection became better understood and interesting relations between complexity classes and time-limited random (incompressible) objects were found. This development could be seen also as finding connections between different notions of randomness (randomness in algorithmic information theory, pseudo-random number generators etc.)

Starting with classical works of Martin-Löf, the notion of algorithmic randomness was closely related to measure theory. Recently it was noted that classical notion of Hausdorff dimension (and similar notions) could be naturally translated to the algorithmic information theory using martingale technique and similar notions.

The first Kolmogorov paper on the subject was called "Three approaches to the definition of the notion of "amount of information", and these approaches were named `combinatorial', `probabilistic' and `algorithmic'. Recently some formal links between these three approaches were noted that allow us to translate some results of algorithmic information theory into combinatorial results and statements about Shannon entropy.

Last but not least there has been a recent development clarifying the distinction between "accidental" information (random noise) and "meaningful information", and how to separate the two. This is a central object of statistics and model selection.

Perspectives

Algorithmic information theory belongs to theoretical computer science and does not claim to be immediately applicable to practice (for example, there is no algorithm to compute Kolmogorov complexity of a given string). However, its ideas act as a sort of inspiration for quite practical applications in learning theory, pattern recognition etc. showing that deep theoretical research becomes useful unexpectedly often.

A comprehensive as well as introductory treatment of Kolmogorov complexity is the monograph by Ming Li and Paul Vitanyi "An Introduction to Kolmogorov Complexity and Its Applications" , Springer-Verlag, New York, 2nd Edition 1997.

Related Dagstuhl Seminar

Keywords

  • Kolmogorov complexity
  • Information theory
  • Randomness
  • Computational complexity

Buchausstellung

Bücher der Teilnehmer 

Buchausstellung im Erdgeschoss der Bibliothek

(nur in der Veranstaltungswoche).

Dokumentation

In der Reihe Dagstuhl Reports werden alle Dagstuhl-Seminare und Dagstuhl-Perspektiven-Workshops dokumentiert. Die Organisatoren stellen zusammen mit dem Collector des Seminars einen Bericht zusammen, der die Beiträge der Autoren zusammenfasst und um eine Zusammenfassung ergänzt.

 

Download Übersichtsflyer (PDF).

Publikationen

Es besteht weiterhin die Möglichkeit, eine umfassende Kollektion begutachteter Arbeiten in der Reihe Dagstuhl Follow-Ups zu publizieren.

Dagstuhl's Impact

Bitte informieren Sie uns, wenn eine Veröffentlichung ausgehend von
Ihrem Seminar entsteht. Derartige Veröffentlichungen werden von uns in der Rubrik Dagstuhl's Impact separat aufgelistet  und im Erdgeschoss der Bibliothek präsentiert.