Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR21-075 | 4th June 2021 01:45

#### Affine Extractors for Almost Logarithmic Entropy

TR21-075
Authors: Eshan Chattopadhyay, Jesse Goodman, Jyun-Jie Liao
Publication: 4th June 2021 02:12
We give an explicit construction of an affine extractor (over $\mathbb{F}_2$) that works for affine sources on $n$ bits with min-entropy $k \ge~ \log n \cdot (\log \log n)^{1 + o(1)}$. This improves prior work of Li (FOCS'16) that requires min-entropy at least $\mathrm{poly}(\log n)$.