Speaker: Madhu Sudan (Harvard)

Title: Communication Complexity of Randomness Manipulation

Abstract: The task of manipulating randomness has been a subject of intense investigation in the theory of computer science. The classical definition of this task consider a single processor massaging random samples from an unknown source and trying to convert it into a sequence of uniform independent bits.  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 surprisingly 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 works with Mitali Bafna (Harvard), Badih Ghazi (Google) and Noah Golowich (Harvard).