Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR10-190 | 9th December 2010 21:33

Improved Constructions of Three Source Extractors

RSS-Feed




TR10-190
Authors: Xin Li
Publication: 9th December 2010 22:26
Downloads: 3434
Keywords: 


Abstract:

We 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}.



ISSN 1433-8092 | Imprint