Low-error two-source extractors for polynomial min-entropy

by Avraham Ben-Aroya, Dean Doron, and Amnon Ta-Shma

Note (July 21, 2016): Unfortunately, the main result of this paper was retracted.
For details, see Revision 1 of ECCC TR16-106.

Oded's comments

This work addresses one of the two questions regarding two-source extractors that was left open by the breakthrough work of Eshan Chattopadhyay and David Zuckerman: Obtaining negligible error probability, where obtaining long output by addressed by Li. The current work achieves improved error bounds, but only for higher levels of min-entropy.

The current work combines ideas from the recent line of works (including the notion of correlation breakers, see Cohen's consolidation) with Bourgain's earlier ideas.

Warning: The perspective on prior works offered by the current write-up seems lacking.

The original abstract

We construct explicit two-source extractors for $n$ bit sources, requiring $n^\alpha$ min-entropy and having error $2^{-n^\beta}$, for some constants $0 < \alpha,\beta < 1$. Previously, constructions for exponentially small error required either min-entropy $0.49n$ \cite{Bou05} or three sources \cite{Li15}. The construction combines somewhere-random condensers based on the Incidence Theorem \cite{Zuc06,Li11}, together with recent machinery surrounding non-malleable extractors.

See ECCC TR16-106.

Back to list of Oded's choices.