Loading jsMath...
Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR15-121 | 25th July 2015 17:38

Extractors for Affine Sources with Polylogarithmic Entropy

RSS-Feed




TR15-121
Authors: Xin Li
Publication: 25th July 2015 20:50
Downloads: 1414
Keywords: 


Abstract:

We give the first explicit construction of deterministic extractors for affine sources over F_2, with entropy k \geq \log^C n for some large enough constant C, where n is the length of the source. Previously the best known results are by Bourgain \cite{Bourgain07}, Yehudayoff \cite{Yehudayoff10} and Li \cite{Li11a}, which require the affine source to have entropy at least \Omega(n/\sqrt{\log \log n}). Our extractor outputs one bit with error n^{-\Omega(1)}.

Our construction is obtained by reducing an affine source to a non-oblivious bit-fixing source, and then applying a deterministic extractor for such sources in the recent breakthrough result of two-source extractors by Chattopadhyay and Zuckerman \cite{CZ15}. To reduce an affine source to a non-oblivious bit-fixing source, we adapt the alternating extraction based approach in previous work on independent source extractors \cite{Li13b} to the affine setting.



ISSN 1433-8092 | Imprint