ECCC-Report TR16-088https://eccc.weizmann.ac.il/report/2016/088Comments and Revisions published for TR16-088en-usWed, 01 Jun 2016 01:58:52 +0300
Paper TR16-088
| Explicit two-source extractors for near-logarithmic min-entropy |
Dean Doron,
Avraham Ben-Aroya,
Amnon Ta-Shma
https://eccc.weizmann.ac.il/report/2016/088We 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}.Wed, 01 Jun 2016 01:58:52 +0300https://eccc.weizmann.ac.il/report/2016/088