Speaker: Elchanan
Mossel

####
Coin flipping from a cosmic source - error correction and sensitivity

We study a new problem related to coin flipping, coding theory, and noise
sensitivity. Consider a source of truly random bits x, and k parties, who
have noisy versions of the source bits y^{i}, where for all i and
j, it holds that Prob[y^{i}_{j} = x_{j}] = 1 -
e, independently for all i

and j. That is, each party sees each bit correctly with probability
1-e, and incorrectly (flipped) with probability e, independently for all

bits and all parties. The parties, who cannot communicate, wish to
agree beforehand on BALANCED boolean functions f_{i} such that

Prob[f_{1}(y^{1}) = ... = f_{k}(y^{k})]
is maximized.
In other words, each party wants to toss a fair coin so that the probability
that all parties have the same coin is maximized. The

functions f_{i}may be thought of as an error correcting procedure
for the source x.

We will discuss exact result for k=2,3 and the asymptotic behavior of
the problem with respect to k, n and e. The analysis uses tools from probability,
discrete Fourier analysis, convexity and discrete symmetrization.

Joint Work with Ryan O'Donnell.

The paper is available in postscript
and pdf