An explicit two-source extractor with min-entropy rate near 4/9

DOI10.1112/S0025579319000238MaRDI QIDQ5225826zbMATH OpenWikidataFDO

Authors Mark Lewko

Publication date 29 July 2019

Published in Mathematika (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1804.05451

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Arithmetic combinatorics; higher degree uniformity (11B30) Combinatorics in computer science (68R05)

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 $.499$. This remained essentially the state of the art until a 2015 breakthrough of 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 $frac2144=.477ldots$, moreover we construct a variant of this extractor which we show extracts from sources with min-entropy rate near $4/9$ = $.444ldots$. 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'ar's generalization of the Guth-Katz incidence theorem.

Recommendations

• Explicit two-source extractors and resilient functions
• Explicit two-source extractors and resilient functions
• Extracting Randomness Using Few Independent Sources
• An efficient reduction from two-source to non-malleable extractors: achieving near-logarithmic min-entropy
• A 2-Source Almost-Extractor for Linear Entropy

Cites work

• A sum-product estimate in finite fields, and applications
• Additive combinatorics
• An explicit incidence theorem in F_p
• An improved point-line incidence bound over arbitrary fields
• Endpoint restriction estimates for the paraboloid over finite fields
• Explicit constructions of extractors and expanders
• Explicit two-source extractors and resilient functions
• Finite field restriction estimates based on Kakeya maximal operator estimates
• Finite field restriction estimates for the paraboloid in high even dimensions
• scientific article; zbMATH DE number 3070115 (Why is no real title available?)
• MORE ON THE SUM-PRODUCT PHENOMENON IN PRIME FIELDS AND ITS APPLICATIONS
• New restriction estimates for the 3-d paraboloid over finite fields
• On a variant of sum-product estimates and explicit exponential sum bounds in prime fields
• On the Erdős distinct distances problem in the plane
• On the number of incidences between points and planes in three dimensions
• On the restriction problem for discrete paraboloid in lower dimension
• Restriction and Kakeya phenomena for finite fields
• Szemerédi-Trotter-type theorems in dimension 3

Cited in

(13)

• How to extract useful randomness from unreliable sources
• From affine to two-source extractors via approximate duality
• An efficient reduction from two-source to non-malleable extractors: achieving near-logarithmic min-entropy
• An Efficient Reduction from Two-Source to Nonmalleable Extractors: Achieving Near-Logarithmic Min-Entropy
• Extractors for a Constant Number of Polynomially Small Min-Entropy Independent Sources
• Counting rectangles and an improved restriction estimate for the paraboloid in F_p^3
• From affine to two-source extractors via approximate duality
• scientific article; zbMATH DE number 7650110 (Why is no real title available?)
• Extractors: low entropy requirements colliding with non-malleability
• Efficient randomized strong 2-source non-malleable extractor for any linear min-entropy
• Two-source and affine non-malleable extractors for small entropy
• A bilinear approach to the finite field restriction problem
• Bit-fixing extractors for almost-logarithmic entropy

This page was built for publication: An explicit two-source extractor with min-entropy rate near $4/9$

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5225826)