Communication Complexity of Randomness Manipulation

Madhu Sudan 

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).