期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2021
卷号：21
语种：English
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：We give an explicit construction of an affine extractor (over F2) that works for affine sources on n bits with min-entropy k logn(loglogn)1+o(1). This improves prior work of Li (FOCS'16) that requires min-entropy at least poly(logn). 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.
