Paper Info
Title
Deterministic Extractors for Additive Sources: Extended Abstract.
Abstract
We propose a new model of a weakly random source that admits randomness extraction. Our model of additive sources includes such natural sources as uniform distributions on arithmetic progressions (APs), generalized arithmetic progressions (GAPs), and Bohr sets, each of which generalizes affine sources. We give an explicit extractor for additive sources with linear min-entropy over both Z(p) and Z(p)(n), for large prime p, although our results over Z(p)(n) require that the source further satisfy a list-decodability condition. As a corollary, we obtain explicit extractors for APs, GAPs, and Bohr sources with linear min-entropy, although again our results over Z(p)(n) require the list-decodability condition.We further explore special cases of additive sources. We improve previous constructions of line sources (affine sources of dimension 1), requiring a field of size linear in n, rather than Omega(n(2)) by Gabizon and Raz. This beats the non-explicit bound of circle minus(n log n) obtained by the probabilistic method. We then generalize this result to APs and GAPs.
Year
DOI
Venue
2015
10.1145/2688073.2688090
ITCS
Keywords
Field
DocType
deterministic extractors, additive combinatorics, small doubling sets, arithmetic progressions, Bohr sets, exponential SUMS
Affine transformation,Prime (order theory),Discrete mathematics,Combinatorics,Bohr model,Probabilistic method,Extractor,Corollary,Time complexity,Mathematics,Randomness
Conference
Citations 
PageRank 
References 
0
0.34
18
Authors
4
Name
Order
Citations
PageRank
Abhishek Bhowmick 00011205.65
Ariel Gabizon2575.79
Thái Hoàng Lê332.08
David Zucherman42588266.65