BEGIN:VCALENDAR VERSION:2.0 PRODID:researchseminars.org CALSCALE:GREGORIAN X-WR-CALNAME:researchseminars.org BEGIN:VEVENT SUMMARY:Joe Miller (University of Wisconsin) DTSTART:20200818T200000Z DTEND:20200818T210000Z DTSTAMP:20260423T005722Z UID:CTA/18 DESCRIPTION:Title: Red undancy of information: lowering effective dimension\nby Joe Miller (U niversity of Wisconsin) as part of Computability theory and applications\n \n\nAbstract\nA natural way to measure the similarity between two infinite \nbinary sequences X and Y is to take the (upper) density of their\nsymmet ric difference. This is the Besicovitch distance on Cantor\nspace. If d(X\ ,Y) = 0\, then we say that X and Y are coarsely\nequivalent. Greenberg\, M .\, Shen\, and Westrick (2018) proved that a\nbinary sequence has effectiv e (Hausdorff) dimension 1 if and only if\nit is coarsely equivalent to a M artin-Löf random sequence. They went\non to determine the best and worst cases for the distance from a\ndimension t sequence to the nearest dimensi on s>t sequence. Thus\, the\ndifficulty of increasing dimension is underst ood.\n\nGreenberg\, et al. also determined the distance from a dimension 1 \nsequence to the nearest dimension t sequence. But they left open the\nge neral problem of reducing dimension\, which is made difficult by the\nfact that the information in a dimension s sequence can be coded (at\nleast so mewhat) redundantly. Goh\, M.\, Soskova\, and Westrick recently\ngave a co mplete solution.\n\nI will talk about both the results in the 2018 paper a nd the more\nrecent work. In particular\, I will discuss some of the codin g theory\nbehind these results. No previous knowledge of coding theory is\ nassumed.\n LOCATION:https://researchseminars.org/talk/CTA/18/ END:VEVENT END:VCALENDAR