Midwest Computability Seminar

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:


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

Kolmogorov extractors and evenly-distributed hypergraphs

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.