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 12021

Computability, Complexity and Randomness

( Jan 08 – Jan 13, 2012 )

(Click in the middle of the image to enlarge)

Please use the following short url to reference this page:




Randomness and information quantity are central notions in computer science that are still undeveloped. Although classical information theory and probability provide formalizations of these notions they do not allow us to measure the information of a specific string or say that a particular real number is random. The definition of the property of randomness and its connection with a measure of information content was obtained in the 1960s and combines different complexity measures.

As witnessed by the three seminars previously organized in Dagstuhl on complexity and randomness(Seminar 9318, Descriptional complexity: a multidisciplinary perspective} in 1993; Seminar 03181 Centennial Seminar on Kolmogorov Complexity and Applications} in 2003; and Seminar 06051 { Kolmogorov Complexity and Applications} in 2006) in recent years there has been an upsurge produced by the people in computability theory that resulted in rapid progress in our understanding of even the most basic notions in randomness, and the solution of old open questions. This 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: Algorithmic Randomness and Complexity, R. Downey and D. Hirschfeldt, Foundations on Computing, Springer, 2010; Computability and Randomness, A. Nies, Oxford University Press, 2009; and An Introduction to Kolmogorov Complexity and Its Applications, M. Li and P. Vitanyi, third Edition, Springer Verlag, 2008.

Seminar 12021 has celebrated significant recent research progress. New results connect the theory of algorithmic randomness with computable analysis. We consider them important because they lead to the naturalness of the notions of algorithmic randomness. For instance, Brattka, Miller, and Nies translated the theorem "every non-decreasing function is almost everywhere differentiable" to the computable world, by showing that a real x is computably random if and only if every computable non-decreasing function is differentiable at x (this work is has not yet appeared as a publication). Similar investigations identified the notions of randomness that correspond to the Lebesgue density and differentiation theorems. J.Franklin and the work of Gács, Hoyrup, and Rojas related Birkhoff's pointwise ergodic theorem in connection with Schnorr randomness.

Considerable results have been obtained for problems on Kolmogorov complexity and computable enumerable sets, in particular, in the degree structure that arises from comparing the complexity of the initial segments of two reals. Barmaplias announced the solution of the already long standing open problem posed by Downey and Hirschfeldt Is there a minimal pair of c.e. reals in the K-degrees? The answer is no.

Since the start of the discipline, the notion of randomness was defined for infinite sequences, or real numbers. The problem posed by Kolmogorov on a notion of randomness of finite objects remains unsolved. This is also the case for arbitrary countable objects. C.Freer made significant progress on the questions When is a graph random? and What is the connection between quasi-random graphs and pseudorandom bit strings? He pointed to an emerging theory of continuous limits of finite combinatorial structures that connects graph limits, property testing, and exchangeable relations.

There was a general consensus on the fact that there is yet no adequate solution to the fundamental problem that high-quality independent random bits are in very short supply. And there are many practical applications rely on randomness (for instance, assigning keys to users of a public-key crypto-system). Randomness extractors are algorithms developed "extract" high-quality random bits from low-entropy sources. Construction of such algorithms is foreseen to be an active research area.

he aim of Seminar 12021 was to bring together researchers covering this spectrum of relevant areas, to report their advances and to discuss the relevant research open questions. The seminar had 50 participants, including the most recognized senior specialists as well as young researchers. The atmosphere was very stimulating and led to new research contacts and collaborations.

Concluding remarks and future plans.

The seminar was well received, as witnessed by the high rate of accepted invitations, and the exemplary degree of involvement by the participants. Due to the broad scope and depth of the problems on algorithmic randomness and information quantity that have been discussed in the presentations and informal discussions, the organizers regard the seminar as a great success. The organizers wish to express their gratitude towards the Scientific Directors of the Dagstuhl Center for their support of this seminar. We foresee the proposal of a new seminar focusing in the interplay between algorithmic randomness and computable analysis.

Organization of the seminar and activities

The seminar consisted in nineteen talks, sessions on open questions, and informal discussions among the participants. The organizers selected the talks in order to have comprehensive lectures giving overview of main topics and communications of new research results. Each day consisted of talks and free time for informal gatherings among participants. There were two main sessions on open questions.

  • Eric Allender (Rutgers University - Piscataway, US) [dblp]
  • Klaus Ambos-Spies (Universität Heidelberg, DE) [dblp]
  • George Barmpalias (Chinese Academy of Sciences - Beijing, CN) [dblp]
  • Bruno Bauwens (University of Porto, PT)
  • Veronica Becher (University of Buenos Aires, AR) [dblp]
  • Laurent Bienvenu (University of Paris VII, FR) [dblp]
  • Harry Buhrman (CWI - Amsterdam, NL) [dblp]
  • Douglas Cenzer (University of Florida - Gainesville, US)
  • Chris J. Conidis (University of Waterloo, CA)
  • Quinn Culver (University of Notre Dame, US)
  • David Diamondstone (Victoria University - Wellington, NZ)
  • Rodney Downey (Victoria University - Wellington, NZ) [dblp]
  • Lance Fortnow (Georgia Institute of Technology - Atlanta, US) [dblp]
  • Johanna N. Y. Franklin (University of Connecticut - Storrs, US) [dblp]
  • Cameron Freer (MIT - Cambridge, US) [dblp]
  • Noam Greenberg (Victoria University - Wellington, NZ) [dblp]
  • Serge Grigorieff (University of Paris VII, FR) [dblp]
  • Pablo A. Heiber (University of Buenos Aires, AR)
  • John Hitchcock (University of Wyoming - Laramie, US)
  • Rupert Hölzl (University of Paris VII, FR) [dblp]
  • Michal Koucký (Czech Academy of Sciences - Prague, CZ) [dblp]
  • Thorsten Kräling (Universität Heidelberg, DE)
  • Antonin Kucera (Charles University - Prague, CZ)
  • Sophie Laplante (University of Paris VII, FR) [dblp]
  • Andrew Lewis (University of Leeds, GB)
  • Bruno Loff (CWI - Amsterdam, NL) [dblp]
  • Elvira Mayordomo (University of Zaragoza, ES) [dblp]
  • Benoît Menoni (Université Paris I, FR)
  • Wolfgang Merkle (Universität Heidelberg, DE) [dblp]
  • Joseph S. Miller (University of Wisconsin - Madison, US) [dblp]
  • Philippe Moser (NUI Maynooth, IE)
  • Satyadev Nandakumar (Indian Institute of Technology - Kanpur, IN)
  • André Otfrid Nies (University of Auckland, NZ) [dblp]
  • Sylvain Perifel (University of Paris VII, FR)
  • Christopher P. Porter (University of Notre Dame, US)
  • Robert Rettinger (FernUniversität in Hagen, DE) [dblp]
  • Andrei Romashchenko (University of Montpellier 2, FR)
  • Ronen Shaltiel (University of Haifa, IL) [dblp]
  • Alexander Shen (University of Marseille, FR) [dblp]
  • Theodore A. Slaman (University of California - Berkeley, US) [dblp]
  • Ludwig Staiger (Martin-Luther-Universität Halle-Wittenberg, DE)
  • Antoine Taveneaux (University of Paris VII, FR)
  • Leen Torenvliet (University of Amsterdam, NL)
  • Daniel Turetsky (Victoria University - Wellington, NZ) [dblp]
  • Stijn Vermeeren (University of Leeds, GB)
  • Variyam N. Vinodchandran (University of Nebraska - Lincoln, US)
  • Paul M. B. Vitanyi (CWI - Amsterdam, NL)
  • Vladimir Viyugin (IITP - Moscow, RU)
  • Osamu Watanabe (Tokyo Institute of Technology, JP)
  • Marius Zimand (Towson University, US)

  • data structures/algorithms/complexity
  • information theory

  • information theory
  • Kolmogorov complexity
  • effective randomness
  • effective ergodic theory
  • effective probability
  • computability theory
  • computational complexity