Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR15-121 | 25th July 2015 17:38

Extractors for Affine Sources with Polylogarithmic Entropy


Authors: Xin Li
Publication: 25th July 2015 20:50
Downloads: 1217


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