Geodesic
Explicit two-source extractors and resilient functions
Eshan Chattopadhyay1 ; David Zuckerman2
1 Department of Computer Science, Cornell University, Ithaca, NY
2 Department of Computer Science, University of Texas at Austin, Austin, TX
Annals of mathematics, Tome 189 (2019) no. 3, pp. 653-705

Voir la notice de l'article provenant de la source Annals of Mathematics website

We explicitly construct an extractor for two independent sources on $n$ bits, each with min-entropy at least $\log^C n$ for a large enough constant $C$. Our extractor outputs one bit and has error $n^{-\Omega(1)}$. The best previous extractor, by Bourgain, required each source to have min-entropy $.499n$.

DOI : 10.4007/annals.2019.189.3.1

Eshan Chattopadhyay 1 ; David Zuckerman 2

1 Department of Computer Science, Cornell University, Ithaca, NY
2 Department of Computer Science, University of Texas at Austin, Austin, TX 
@article{10_4007_annals_2019_189_3_1,
     author = {Eshan Chattopadhyay and David Zuckerman},
     title = {Explicit two-source extractors and resilient functions},
     journal = {Annals of mathematics},
     pages = {653--705},
     publisher = {mathdoc},
     volume = {189},
     number = {3},
     year = {2019},
     doi = {10.4007/annals.2019.189.3.1},
     mrnumber = {3961081},
     zbl = {07097488},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.4007/annals.2019.189.3.1/}
}
TY  - JOUR
AU  - Eshan Chattopadhyay
AU  - David Zuckerman
TI  - Explicit two-source extractors and resilient functions
JO  - Annals of mathematics
PY  - 2019
SP  - 653
EP  - 705
VL  - 189
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.4007/annals.2019.189.3.1/
DO  - 10.4007/annals.2019.189.3.1
LA  - en
ID  - 10_4007_annals_2019_189_3_1
ER  - 
%0 Journal Article
%A Eshan Chattopadhyay
%A David Zuckerman
%T Explicit two-source extractors and resilient functions
%J Annals of mathematics
%D 2019
%P 653-705
%V 189
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.4007/annals.2019.189.3.1/
%R 10.4007/annals.2019.189.3.1
%G en
%F 10_4007_annals_2019_189_3_1
Eshan Chattopadhyay; David Zuckerman. Explicit two-source extractors and resilient functions. Annals of mathematics, Tome 189 (2019) no. 3, pp. 653-705. doi: 10.4007/annals.2019.189.3.1

Cité par Sources :