Can I read Coin flipping from a cosmic source: On error correction of truly random bits on EtoBox?

Coin flipping from a cosmic source: On error correction of truly random bits by Elchanan Mossel; Ryan O'Donnell is a Mathematics article available to read on EtoBox.

What is Coin flipping from a cosmic source: On error correction of truly random bits about?

## Abstract 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__ = __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__. On the other hand, for large values of __k__, better protocols exist. We study general properties of the optimal protocols

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

Author

Elchanan Mossel; Ryan O'Donnell

Publisher

John Wiley and Sons; Wiley (John Wiley & Sons); John Wiley & Sons Inc.; Wiley (ISSN 1042-9832)

Published

2005

Language

EN

Field

Mathematics (Physical Sciences)