Efficient Two-Sources Randomness Extraction: A Challenge from the mid-1980s

a brief description

The challenge is constructing an explicit two-source randomness extractors with parameters that meet the existential counting argument. For starters, we highlight the problem of extracting a single bit from two sources that have arbitrary small constant rate, where the extracted bit should have arbitrary small constant bias.

Update (July 2015):A recent breakthrough by Eshan Chattopadhyay and David Zuckerman comes very close to resolving this open problem: It extracts a single bit from sources of polylogarithmic min-entropy.

more details

My paper with Benny Chor (FOCS'85 and [SICOMP, Vol. 17, No. 2, 1988]) shows the existence of a function $f:\{0,1\}^n\times\{0,1\}^n\to\{0,1\}^m$ that is an extractor of error $\e$ for pairs of $(n,k)$-sources, provided that $m < 2k-2\log_(m/\e)$. (The proof uses a counting argument that is based on the fact that it suffices to consider flat sources.) The challenge is to provided a polynomial-time computable function $f$ that meets the foregoing parameters.
For starters, let us focus on the case that $m=1$. In this case, the said paper provides a very simple function (i.e., inner-product) that constitutes an extractor of error $\e$ for pairs of $(n,k)$-sources, provided that $k > (n/2) + 2\log_(2/\e)$. This result refers to min-entropy rate (i.e., $k/n$) one half, and a concrete challenge is to extend this result to any constant min-entropy rate (i.e., $(n,k)$-sources such that $k=\Omega(n)$).
Note that, under a reasonable conjecture regarding the Paley Graph (i.e., a graph with vertex set $Z_p$, for a prime $p$, such that $(i,j)$ is an edge iff $i-j$ is a quadratic residue modulo $p$), the corresponding function (i.e., $f(i,j)=1$ iff $(i,j)$ is an edge) is an extractor of exponentially vanishing error for pairs of sources of any constant min-entropy rate (see [CG, Corr 11, p. 240]).
This is how things stood for almost two decades, but renewed interest in the problem (pioneered in 2004 by Barak, Impagliazzo and Wigderson), led to very significant progress on closely related problems (e.g., the problem of extraction from three sources, and the construction of two-sources dispersers)[*]. As for the problem of two-source extraction, we mention the well-known result of Bourgain (2005) that provides an explicit construction for min-entropy rate 0.4999.

[*] The problem of extraction from three sources is much more important for the original motivation (of actually using such extractors to purify randomness various applications), but one may argue that the construction of two-sources dispersers is technically more related to the problem of constructing two-sources extractors.


Back to list of Oded's choices.