Description
Combinatorics Seminar.
Speaker: Madhu Sudan (Harvard University)
Date-Time: Monday, June 3, 2019. 4-5 PM.
Venue: Ramanujan Hall, Department of Mathematics.
Title: Communication Complexity of Randomness Manipulation
Abstract: The task of manipulating randomness has been a subject of
intense investigation in computational complexity with dispersers,
extractors, pseudorandom generators, condensers, mergers being just a
few of the objects of interest. All these tasks consider a single
processor massaging random samples from an unknown source.
In this talk I will talk about a less studied setting where randomness
is distributed among different players who would like to convert this
randomness to others forms with relatively little communication. For
instance players may be given access to a source of biased correlated
bits, and their goal may be to get a common random bit out of this
source. Even in the setting where the source is known this can lead to
some interesting questions that have been explored since the 70s with
striking constructions and some suprisingly hard questions. After
giving some background, I will describe a recent work which explores
the task of extracting common randomness from correlated sources with
bounds on the number of rounds of interaction.
Based on joint work with Mitali Bafna (Harvard), Badih Ghazi (Google)
and Noah Golowich (Harvard).