ECCC-Report TR15-121https://eccc.weizmann.ac.il/report/2015/121Comments and Revisions published for TR15-121en-usSat, 25 Jul 2015 20:50:44 +0300
Paper TR15-121
| Extractors for Affine Sources with Polylogarithmic Entropy |
Xin Li
https://eccc.weizmann.ac.il/report/2015/121We 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.Sat, 25 Jul 2015 20:50:44 +0300https://eccc.weizmann.ac.il/report/2015/121