ECCC-Report TR10-190https://eccc.weizmann.ac.il/report/2010/190Comments and Revisions published for TR10-190en-usThu, 09 Dec 2010 22:26:26 +0200
Paper TR10-190
| Improved Constructions of Three Source Extractors |
Xin Li
https://eccc.weizmann.ac.il/report/2010/190We study the problem of constructing extractors for independent weak random sources. The probabilistic method shows that there exists an extractor for two independent weak random sources on $n$ bits with only logarithmic min-entropy. However, previously the best known explicit two source extractor only achieves min-entropy $0.499n$ \cite{Bourgain05}, and the best known three source extractor only achieves min-entropy $n^{0.9}$ \cite{Rao06}. It is a long standing open problem to construct extractors that work for smaller min-entropy.
In this paper we construct an extractor for three independent weak random sources on $n$ bits with min-entropy $n^{1/2+\delta}$, for any constant $0<\delta<1/2$. This improves the previous best result of \cite{Rao06}. In addition, we consider the problem of constructing extractors for three independent weak sources, such that one of the sources is significantly shorter than the min-entropy of the other two, in the spirit of \cite{RaoZ08}. We give an extractor that works in the case where the longer, $n$-bit sources only have min-entropy $\polylog(n)$, and the shorter source also has min-entropy $\polylog(n)$. This improves the result of \cite{RaoZ08}.
We also study the problem of constructing extractors for affine sources over $\GF(2)$. Previously the best known deterministic extractor for $n$-bit affine sources in this case achieves entropy $n/\sqrt{\log \log n}$ \cite{Yehudayoff10, Li10}. In this paper we construct an extractor for two independent affine sources with entropy $n^{1/2+\delta}$, for any constant $0<\delta<1/2$.
Our constructions mainly use the extractors for somewhere random sources in \cite{Rao06, Rao09} and the lossless condenser in \cite{GuruswamiUV07}. Thu, 09 Dec 2010 22:26:26 +0200https://eccc.weizmann.ac.il/report/2010/190