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.

logic

Audience: researchers in the topic

Computability theory and applications

Series comments: Description: Computability theory, logic

The goal of this endeavor is to run a seminar on the platform Zoom on a weekly basis, perhaps with alternating time slots each of which covers at least three out of four of Europe, North America, Asia, and New Zealand/Australia. While the meetings are always scheduled for Tuesdays, the timezone varies, so please refer to the calendar on the website for details about individual seminars.