Effective Randomness

This workshop, sponsored by AIM and the NSF, 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.

The workshop will differ from typical conferences in some regards. Participants will be invited to suggest open problems and questions before the workshop begins, and these will be posted on the workshop website. These include specific problems on which there is hope of making some progress during the workshop, as well as more ambitious problems which may influence the future activity of the field. Lectures at the workshop will be focused on familiarizing the participants with the background material leading up to specific problems, and the schedule will include discussion and parallel working sessions.

The deadline to apply for support to participate in this workshop has passed.

For more information email workshops@aimath.org

Plain text announcement or brief announcement.

Go to the American Institute of Mathematics.
Return to the AIM Research Conference Center.