Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR15-034 | 8th March 2015 17:51

Three-Source Extractors for Polylogarithmic Min-Entropy


Authors: Xin Li
Publication: 8th March 2015 20:01
Downloads: 2238


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.

ISSN 1433-8092 | Imprint