Applications are closed
for this workshop

Algorithmic randomness

August 10 to August 14, 2020

at the

American Institute of Mathematics, San Jose, California

organized by

Denis R. Hirschfeldt, Joseph S. Miller, Jan Reimann, and Theodore A. Slaman

This workshop, sponsored by AIM and the NSF, will be devoted to algorithmic randomness and its applications. Combining computability and probability, algorithmic randomness allows for a pointwise approach to many concepts that are classically measure-based, such as entropy and Hausdorff dimension. Recent results in the area indicate the applicability of algorithmic randomness to a wide variety of questions, from the fractal geometry of sets in Euclidean spaces to effective diophantine approximation.

The workshop will focus on several particularly promising applications:

  • Point-to-set principles: there is a tight correspondence between the classical Hausdorff dimension of a set and the effective Hausdorff dimension of its points. Questions about the Hausdorff dimension of a set can then be translated into questions about the relative randomness and effective dimension of single points. For example, if $a$ and $b$ are points in $(n-1)$-dimensional Euclidean space, and $x$ is a real Martin-Löf random with respect to $(a,b)$, what is the effective Hausdorff dimension of $(x,ax+b)$? This is closely connected to the Kakeya conjecture.

  • Effective Fourier dimension: Fourier measures are characterized by the asymptotic behavior of their Fourier-Stieltjes coefficients. If a real is random with respect to a non-trivial Fourier measure, it exhibits randomness in terms of a linear lower bound on its Kolmogorov complexity on the one hand, and strong combinatorial randomness on the other hand, because any such real has to be absolutely normal. Understanding which reals are random with respect to a Fourier measure would help shed light on the nature of Salem sets, that is, sets for which Hausdorff dimension and Fourier dimension coincide.

  • Redundancy of Information. The effective dimension of a real can be altered by changing individual bits of its binary expansion. The distance between the original and the altered sequence can be measured by the Besicovitch distance in Cantor space. If we want to reduce dimension from $s$ to $t$, what is the best bound, in general, on the distance from a given sequence of dimension $s$ to the nearest sequence of dimension $t$?

This event will be run as an AIM-style workshop. 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

Plain text announcement or brief announcement.