June 3, 2019 - June 7, 2019
Public Access Category: All |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
- Time:
- 4:00pm-5:00pm
- Location:
- Ramanujan Hall, Department of Mathematics
- 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).
- Time:
- 4:00pm
- Location:
- Ramanujan Hall, Department of Mathematics
- Description:
- CACAAG Seminar
Speaker: Srikanth Srinivasan.
Time: Thursday, June 6, 4pm.
Venue: Ramanujan Hall.
Title: Algebraic complexity theory and connections to Hilbert functions
(Lecture III).
Abstract: In a few lectures, I will introduce some of the main
problems in Algebraic Complexity theory and some of the techniques
that have been used to make progress on them. The techniques are
closely related to Hilbert functions and Young flattenings.