Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR15-121 | 25th July 2015 17:38

#### Extractors for Affine Sources with Polylogarithmic Entropy

TR15-121
Authors: Xin Li
Publication: 25th July 2015 20:50
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)}$.