## 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.