Processing math: 100%

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 H1(t)H1(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.