## Three-Source Extractors for Polylogarithmic Min-Entropy

by Xin Li

#### Oded's comments

Another amazing result of Xin Li,
improving over his prior work:
The abstract talks for itself.

#### The original abstract

We continue the study of constructing explicit extractors for independent
general weak random sources. The ultimate goal is to give a construction
that matches what is given by the probabilistic method --- an extractor for
two independent $n$-bit weak random sources with min-entropy as small as
$\log n+O(1)$. Previously, the best known result in the two-source case is
an extractor by Bourgain \cite{Bourgain05}, which works for min-entropy
$0.49n$; and the best known result in the general case is an earlier work
of the author \cite{Li13b}, which gives an extractor for a constant number
of independent sources with min-entropy $polylog(n)$. However, the constant
in the construction of \cite{Li13b} depends on the hidden constant in the
best known
seeded extractor, and can be large; moreover the error in that construction
is only $1/poly(n)$.

In this paper, we make two important improvements over the result in
\cite{Li13b}. First, we construct an explicit extractor for \emph{three}
independent sources on $n$ bits with min-entropy $k \geq polylog(n)$. In
fact, our extractor works for one independent source with poly-logarithmic
min-entropy and another independent block source with two blocks each
having poly-logarithmic min-entropy. Thus, our result is nearly optimal,
and the next step would be to break the $0.49n$ barrier in two-source
extractors. Second, we improve the error of the extractor from $1/poly(n)$
to $2^{-k^{\Omega(1)}}$, which is almost optimal and crucial for
cryptographic applications. Some of the techniques developed here may be of
independent interests.

See ECCC TR15-034.

Back to
list of Oded's choices.