Coin flipping from a cosmic source: On error correction of truly random bits
| dc.creator | Mossel, Elchanan | |
| dc.creator | O'Donnell, Ryan | |
| dc.date | 2004-06-24 | |
| dc.date.accessioned | 2026-07-07T05:09:41Z | |
| dc.date.available | 2026-07-07T05:09:41Z | |
| dc.description | We study a problem related to coin flipping, coding theory, and noise sensitivity. Consider a source of truly random bits $x \in \bits^n$, and $k$ parties, who have noisy versions of the source bits $y^i \in \bits^n$, where for all $i$ and $j$, it holds that $\Pr[y^i_j = x_j] = 1 - \eps$, 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 {\em balanced} functions $f_i : \bits^n \to \bits$ such that $\Pr[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 functions $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(x^i) = y^i_1$. 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 $\eps$. Our analysis uses tools from probability, discrete Fourier analysis, convexity and discrete symmetrization. | |
| dc.identifier | https://arxiv.org/abs/math/0406504 | |
| dc.identifier | http://arxiv.org/abs/math/0406504 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/71669 | |
| dc.subject | Probability | |
| dc.subject | Combinatorics | |
| dc.title | Coin flipping from a cosmic source: On error correction of truly random bits | |
| dc.type | text |