| Coin flipping from a cosmic source: On error correction of truly random bits (2002) | |||||||||||||||
Abstract | |||||||||||||||
| We study a new 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 versions of the source bits y^i ∈ {0, 1}^n, where for all i and j, it holds that P[y j = x j ] = 1 - ε, independently for all i and j. That is, each party sees each bit correctly with probability 1 - ε, and incorrectly (ipped) with probability ε, independently for all bits and all parties. The parties, who cannot communicate, wish to agree beforehand on balanced functions f i : f0; 1g ! f0; 1g such that )] 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. When K = 2, 3 no error... | |||||||||||||||
Publication details | |||||||||||||||
| |||||||||||||||