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 yi, where for all i and j, it holds that Prob[yij = xj] = 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 fi such that
Prob[f1(y1) = ... =  fk(yk)] 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 fimay 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