The speaker for next week’s theory seminar will be Benjamin Koch (see title and abstract below). We will meet next Tuesday at 2pm in the theory lab.

Title

The uniform computational strength of high-dimensional points

Abstract

Hausdorff dimension, which allows us to distinguish between the sizes of sets with Lebesgue measure 0, is one of the most studied aspects of geometric measure theory. Within the last decade, the so-called point-to-set principle of J. Lutz and N. Lutz defined the Hausdorff dimension of subsets of R^n in terms of the information density of their points, as measured via Kolmogorov complexity. Essentially, sets with high Hausdorff dimension must contain points of arbitrarily high information density, which we call effective dimension, relative to any oracle. This can be formulated as a problem from the perspective of Weihrauch reducibility: given a set, an oracle, and a tolerance, how difficult is it to obtain a point in that set whose effective dimension relative to that oracle is sufficiently close to the Hausdorff dimension of the set?

We discuss this problem, and variations of it, for increasingly complicated subsets of Cantor space (the space of infinite binary sequences). We show that the problem HDAC (Hausdorff dimension-approximating choice) for closed sets, as described above, is strong enough to compute the problems of closed choice on the reals and of finding, given a bounded sequence of natural numbers as well as the bound, some number which appears in the sequence infinitely many times. We also discuss the best available upper bound for HDAC. For G_delta subsets of Cantor space, we show that HDAC lies in the less-well-explored region of the Weihrauch lattice above choice on Baire space and below the analogues of Pi^1_1 comprehension in reverse mathematics. Time permitting, we will also discuss the analogous problems of HDWC (Hausdorff dimension-witnessing choice) which allow us to obtain a point whose effective dimension is exactly the Hausdorff dimension of the set.