Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR16-088 | 1st June 2016 01:27

Explicit two-source extractors for near-logarithmic min-entropy

RSS-Feed




TR16-088
Authors: Avraham Ben-Aroya, Dean Doron, Amnon Ta-Shma
Publication: 1st June 2016 01:58
Downloads: 1942
Keywords: 


Abstract:

We explicitly construct extractors for two independent $n$-bit sources of $(\log n)^{1+o(1)}$ min-entropy. Previous constructions required either $\mathrm{polylog}(n)$ min-entropy \cite{CZ15,Meka15} or five sources \cite{Cohen16}.

Our result extends the breakthrough result of Chattopadhyay and Zuckerman \cite{CZ15} and uses the non-malleable extractor of Cohen \cite{Cohen16}. The main new ingredient in our construction is a somewhere-random condenser with a small entropy gap, used as a sampler. We construct such somewhere-random condensers using the error reduction mechanism of Raz et al. \cite{RRV99} together with the high-error, constant degree dispersers of Zuckerman \cite{Zuc06}.



ISSN 1433-8092 | Imprint