Joe Miller (University of Wisconsin)

August 18, 2020 @ 10:00 am – 11:00 am

Title: Redundancy of information: lowering effective dimension
by Joe Miller (University of Wisconsin) as part of Computability theory and applications

A natural way to measure the similarity between two infinite
binary sequences X and Y is to take the (upper) density of their
symmetric difference. This is the Besicovitch distance on Cantor
space. If d(X,Y) = 0, then we say that X and Y are coarsely
equivalent. Greenberg, M., Shen, and Westrick (2018) proved that a
binary sequence has effective (Hausdorff) dimension 1 if and only if
it is coarsely equivalent to a Martin-Löf random sequence. They went
on to determine the best and worst cases for the distance from a
dimension t sequence to the nearest dimension s>t sequence. Thus, the
difficulty of increasing dimension is understood.

Greenberg, et al. also determined the distance from a dimension 1
sequence to the nearest dimension t sequence. But they left open the
general problem of reducing dimension, which is made difficult by the
fact that the information in a dimension s sequence can be coded (at
least somewhat) redundantly. Goh, M., Soskova, and Westrick recently
gave a complete solution.

I will talk about both the results in the 2018 paper and the more
recent work. In particular, I will discuss some of the coding theory
behind these results. No previous knowledge of coding theory is