Coin flipping from a cosmic source: On error correction of truly random bits

We study a problem related to coin flipping, coding theory, and noise sensitivity. Consider a source of truly random bits x ∈ {0, 1} n , and k parties, who have noisy version of the source bits y i ∈ {0, 1} n , when for all i and j , it holds that P [ y   j i= x j ] = 1 − ϵ, independently for all i and j . That is, each party sees each bit correctly with probability 1 − ϵ, and incorrectly (flipped) with probability ϵ, independently for all bits and all parties. The parties, who cannot communicate, wish to agree beforehand on balanced functions f i : {0, 1} n → {0, 1} such that P [ 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 function f i may be thought of as an error correcting procedure for the source x . When k = 2,3, no error correction is possible, as the optimal protocol is given by f i ( y i ) = y   1 i . On the other hand, for large values of k , better protocols exist. We study general properties of the optimal protocols and the asymptotic behavior of the problem with respect to k, n , and ϵ. Our analysis uses tools from probability, discrete Fourier analysis, convexity, and discrete symmetrization. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2005