ECCC-Report TR15-034https://eccc.weizmann.ac.il/report/2015/034Comments and Revisions published for TR15-034en-usSun, 08 Mar 2015 20:01:15 +0200
Paper TR15-034
| Three-Source Extractors for Polylogarithmic Min-Entropy |
Xin Li
https://eccc.weizmann.ac.il/report/2015/034We 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.
Sun, 08 Mar 2015 20:01:15 +0200https://eccc.weizmann.ac.il/report/2015/034