Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR16-106 | 21st July 2016 10:23

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

RSS-Feed




Revision #1
Authors: Avraham Ben-Aroya, Dean Doron, Amnon Ta-Shma
Accepted on: 21st July 2016 10:23
Downloads: 1016
Keywords: 


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.



Changes to previous version:

The paper was retracted.


Paper:

TR16-106 | 15th July 2016 15:53

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





TR16-106
Authors: Avraham Ben-Aroya, Dean Doron, Amnon Ta-Shma
Publication: 16th July 2016 16:37
Downloads: 1138
Keywords: 


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.



ISSN 1433-8092 | Imprint