Revision #1 Authors: Avraham Ben-Aroya, Dean Doron, Amnon Ta-Shma

Accepted on: 21st July 2016 10:23

Downloads: 1057

Keywords:

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.

The paper was retracted.

TR16-106 Authors: Avraham Ben-Aroya, Dean Doron, Amnon Ta-Shma

Publication: 16th July 2016 16:37

Downloads: 1190

Keywords:

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.