No.047 Algorithmic Randomness and Complexity

Shonan Village Center
8 ? 12 September, 2014

Information and randomness are fundamental notions of computer science. Their practical applications are ever increasing. For instance, a recent volume of Communications of the ACM describes an application of (approximations of) Kolmogorov complexity to voice recognition. Kolmogorov complexity can be used to measure information distance in a natural and context-free way, and can be used in areas as diverse as computational biology, music evolution, data mining, and at least 20 other areas. Classical information theory and probability provide formalizations, but do not allow us to speak of the information content of a specific string or to say that a particular infinite binary sequence is random. These notions were formalized in the 1960s with the introduction of Kolmogorov complexity and Martin-Loef randomness. The first measures the complexity (or information content) of finite binary strings, while the second captures the intuition that a random infinite binary sequence has no “distinguishing features”. There are also characterizations of Martin-Loef randomness that capture the alternative intuitions that a random sequence is unpredictable and incompressible, the latter connecting Martin-Loef randomness to Kolmogorov complexity.

In recent years the people working in computability theory have produced a surge that resulted in rapid progress in our understanding of even the most basic notions, and in the solution of old open questions. This progress has changed and is still changing the landscape and opened up new avenues of research. An evidence of this activity has been the publication of two new books in the area, and the new edition of an already classical one.

1. Algorithmic Randomness and Complexity, R. Downey and D. Hirschfeldt, Theory and Applications of Computability, Springer, 2010.
2. Computability and Randomness, A. Nies, Oxford University Press, 2009.
3. An Introduction to Kolmogorov Complexity and Its Applications, M. Li and P. Vitanyi. Third Edition, Springer Verlag, 2008.

Additionally, two of the proposers have been invited to the International Congress of Mathematicians to speak on algorithmic randomness, and a number of special issues of Computer Science Journals have been devoted to this area.

Research on the notions of information and randomness has drawn on methods and ideas from computability theory and computational complexity, as well as from core mathematical subjects like measure theory and information theory. The proposed list of invitees is balanced with respect to the various fields and reflects our aim to bring together the leading researchers from these areas. A major goal of the seminar is to bring together researchers to discuss the current open problems.