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)]
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