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.
