American Institute of Mathematics, Palo Alto, California
Denis Hirschfeldt and Joseph Miller
Topics for the workshop will include effective notions of randomness such as Martin--Löf randomness; measures of relative randomness; effective dimension; Kolmogorov complexity and other concepts from algorithmic information theory; and interactions with computability theory and complexity theory.
We hope the discussions at this workshop will help us move closer to the solution of open problems such as the ones detailed in the recent paper Randomness and computability: open questions by Miller and Nies. Examples of such open problems include the power of computable nonmonotonic betting strategies, and the possible interactions between Turing degrees of K-trivial sets, Martin-Löf random sets, and sets of positive effective dimension. We also hope that bringing together such a diverse group will uncover new questions and lines of research that may help define the future of this area. Speculative interdisciplinary questions include whether definitions of "usefulness of information" obtained in the context of complexity theory have interesting analogs in computability theory, and whether an effectivization of the Haar null sets from descriptive set theory would provide a useful notion of effective randomness in general Polish groups.
The workshop schedule.
A report on the workshop activities.
A list of open problems.
The randomness Wiki.