Correlation Distillation On Trees
Phase Transitions in Computation and Reconstruction
March 08, 2005 11:30 AM to 11:50 AM
Speakers:
|
 |
Summary: |
Suppose we fix an undirected tree and think of it as a network, with
the nodes being 'players' and the edges being binary symmetric
channels. One player gets a uniformly random bit string of length n
and broadcasts it to the other players along the edges. Now the
players have correlated random strings, and they would like to agree
on a shared random bit -- without communicating. Specifically, each
applies a balanced boolean function to their string and we hope that
all players output the same bit. What function or functions should
the players use, and how well can they do? This question has some
surprising answers and connections to Kahn-Kalai-Linial theorem and
Kalai's "It Ain't Over Till It's Over" problem.
Joint work with Elchanan Mossel (Berkeley), Oded Regev
(Tel Aviv), Jeffrey Steif (Chalmers), and Benjamin Sudakov
(Princeton). |
Keywords: |
Phase Transition;Computation;Reconstruction |
|
|
