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.