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.

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.

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.