Effective Randomness

August 7 to August 11, 2006

at the

American Institute of Mathematics, San Jose, California

organized by

Denis Hirschfeldt and Joseph Miller

Original Announcement

This workshop will bring together researchers who have studied effective randomness at different times, with different motivations, and drawing from different academic backgrounds, with an aim toward increasing communication and collaboration, and developing broad shared research goals and a coherent research community.

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.

Material from the workshop

A list of participants.

The workshop schedule.

A report on the workshop activities.

The randomness Wiki.