Improved Two-Source Extractors, and Affine Extractors for Polylogarithmic Entropy

摘要

In a recent breakthrough [1], Chattopadhyay and Zuckerman gave an explicit two-source extractor for min-entropy k ≥ logC n for some large enough constant C, where n is the length of the source. However, their extractor only outputs one bit. In this paper, we improve the output of the two-source extractor to kΩ(1), while the error remains n-Ω(1) and the extractor remains strong in the second source. In the non-strong case, the output can be increased to k. Our improvement is obtained by giving a better extractor for (q, t, γ) non-oblivious bit-fixing sources, which can output tΩ(1) bits instead of one bit as in [1]. We also give the first explicit construction of deterministic extractors for affine sources over F2, with entropy k ≥ logC n for some large enough constant C, where n is the length of the source. Previously the best known results are by Bourgain [2], Yehudayoff [3] and Li [4], which require the affine source to have entropy at least Ω(n/√log log n). Our extractor outputs kΩ(1) bits with error n-Ω(1). This is done by reducing an affine source to a non-oblivious bit-fixing source, where we adapt the alternating extraction based approach in previous work on independent source extractors [5] to the affine setting. Our affine extractors also imply improved extractors for circuit sources studied in [6]. We further extend our results to the case of zero-error dispersers, and give two applications in data structures that rely crucially on the fact that our two-source or affine extractors have large output size.