ECCC-Report TR21-075https://eccc.weizmann.ac.il/report/2021/075Comments and Revisions published for TR21-075en-usFri, 04 Jun 2021 02:12:08 +0300
Paper TR21-075
| Affine Extractors for Almost Logarithmic Entropy |
Eshan Chattopadhyay,
Jesse Goodman,
Jyun-Jie Liao
https://eccc.weizmann.ac.il/report/2021/075We 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)$.
Our construction is based on the framework of using correlation breakers and resilient functions, a paradigm that was also used by Li. On a high level, the key sources of our improvement are based on the following new ingredients: (i) A new construction of an affine somewhere random extractor, that we use in a crucial step instead of a linear seeded extractor (for which optimal constructions are not known) that was used by Li. (ii) A near optimal construction of a correlation breaker for linearly correlated sources. The construction of our correlation breaker takes inspiration from an exciting line of recent work that constructs two-source extractors for near logarithmic min-entropy.Fri, 04 Jun 2021 02:12:08 +0300https://eccc.weizmann.ac.il/report/2021/075