Midwest Computability Seminar

XXVIII
Part ii


The Midwest Computability Seminar will meet remotely in the winter and spring of 2022, jointly with the Computability Theory and Applications Online Seminar. The recurring Zoom link is:

https://notredame.zoom.us/j/99754332165?pwd=RytjK1RFZU5KWnZxZ3VFK0g4YTMyQT09

Meeting ID: 997 5433 2165

Passcode: midwest


slides    Panopto video    YouTube video


DATE: Monday, February 7th, 2022

TIME: 3:30 - 4:30 PM Central Time


SPEAKER: Matthew Harrison-Trainor - University of Michigan

TITLE: Kolmogorov extractors and evenly-distributed hypergraphs

ABSTRACT: Suppose that we have a string which has some amount of randomness and we want to produce from it, in an effective way, a string which is more random. Though we cannot do this, it is possible to produce two strings, at least one of which is more random than the original string. Moreover, the more strings we are allowed to produce, the more we can increase the randomness. How much can we increase the randomness, and how many strings are required? This question turns out to be related to a purely graph-theoretic question about how evenly the edges of a hypergraph can be distributed.



Past and Future Sessions

Previous Seminars:

If you haven't been receiving the announcements and would like to be included in the list, send an email to drh@math.uchicago.edu.