Logic Seminar

Linda Brown WestrickUniversity of Connecticut, Storrs
Increasing dimension $s$ to dimension $t$ with few changes

Tuesday, September 26, 2017 - 2:55pm
Malott 206

We show that for every $s < t$ in $[0,1]$, every sequence of effective dimension $s$ can be changed on density at most $H^{-1}(t) - H^{-1}(s)$ of its bits in order to obtain a sequence of effective dimension $t$, where $H$ is the Shannon binary entropy function. This is the infinitary analogue of a known finite result, but passing from the finite to the infinite requires, among other techniques, a convexity argument with a puzzling dichotomy. The density bound is the best possible, and this answers a question which was left open at the time of previous presentations on this subject. Joint work with Noam Greenberg, Joe Miller and Sasha Shen.