# 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

## Original Announcement

This workshop 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$?

## Material from the workshop

A list of participants.

The workshop schedule.

A report on the workshop activities.