ECCC-Report TR16-106https://eccc.weizmann.ac.il/report/2016/106Comments and Revisions published for TR16-106en-usThu, 21 Jul 2016 10:23:22 +0300
Revision 1
| Low-error two-source extractors for polynomial min-entropy |
Dean Doron,
Amnon Ta-Shma,
Avraham Ben-Aroya
https://eccc.weizmann.ac.il/report/2016/106#revision1We 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.Thu, 21 Jul 2016 10:23:22 +0300https://eccc.weizmann.ac.il/report/2016/106#revision1
Paper TR16-106
| Low-error two-source extractors for polynomial min-entropy |
Dean Doron,
Amnon Ta-Shma,
Avraham Ben-Aroya
https://eccc.weizmann.ac.il/report/2016/106We 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.Sat, 16 Jul 2016 16:37:35 +0300https://eccc.weizmann.ac.il/report/2016/106