Article contents
AN EXPLICIT TWO-SOURCE EXTRACTOR WITH MIN-ENTROPY RATE NEAR $4/9$
Published online by Cambridge University Press: 24 July 2019
Abstract
In 2005 Bourgain gave the first explicit construction of a two-source extractor family with min-entropy rate less than $1/2$. His approach combined Fourier analysis with innovative but inefficient tools from arithmetic combinatorics and yielded an unspecified min-entropy rate which was greater than $0.499$. This remained essentially the state of the art until a 2015 breakthrough by Chattopadhyay and Zuckerman in which they gave an alternative approach which produced extractors with arbitrarily small min-entropy rate. In the current work, we revisit the Fourier analytic approach. We give an improved analysis of one of Bourgain’s extractors which shows that it in fact extracts from sources with min-entropy rate near $\frac{21}{44}=0.477\ldots .$ Moreover, we construct a variant of this extractor which we show extracts from sources with min-entropy rate near $4/9=0.444\ldots .$ While this min-entropy rate is inferior to Chattopadhyay and Zuckerman’s construction, our extractors have the advantage of exponential small error, which is important in some applications. The key ingredient in these arguments is recent progress connected to the restriction theory of the finite field paraboloid by Rudnev and Shkredov. This in turn relies on a Rudnev’s point–plane incidence estimate, which in turn relies on Kollár’s generalization of the Guth–Katz incidence theorem.
MSC classification
- Type
- Research Article
- Information
- Copyright
- Copyright © University College London 2019
References
- 5
- Cited by