BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/967
DTSTAMP:20230914T125945Z
SUMMARY:Communication Complexity of Randomness Manipulation
DESCRIPTION:Speaker: Madhu Sudan (Harvard John A. Paulson School of\nEngine
 ering and Applied Sciences\nCambridge\, MA 02138\nUnited States of America
 )\n\nAbstract: \nAbstract:  The task of manipulating randomness has been 
 a subject of intense investigation in computational complexity with disper
 sers\, extractors\, pseudorandom generators\, condensers\, mergers being j
 ust a few of the objects of interest. All these tasks consider a single pr
 ocessor massaging random samples from an unknown source.\nIn this talk I w
 ill talk about a less studied setting where randomness is distributed amon
 g different players who would like to convert this randomness to others fo
 rms with relatively little communication. For instance players may be give
 n 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 h
 ard questions. After giving some background\, I will describe a recent wor
 k which explores the task of extracting common randomness from correlated 
 sources with bounds on the number of rounds of interaction.\nBased on join
 t work with Mitali Bafna (Harvard)\, Badih Ghazi (Google) and Noah Golowic
 h (Harvard).\n
URL:https://www.tcs.tifr.res.in/web/events/967
DTSTART;TZID=Asia/Kolkata:20190529T110000
DTEND;TZID=Asia/Kolkata:20190529T120000
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR