Paper Info
Title
Extractors for Near Logarithmic Min-Entropy
Abstract
The main contribution of this work is an explicit construction of extractors for near logarithmic min-entropy. For any δ > 0 we construct an extractor for O(1/δ) n-bit sources with min-entropy (logn) <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1+δ</sup> . This is most interesting when δ is set to a small constant, though the result also yields an extractor for O(log logn) sources with logarithmic min-entropy. Prior to this work, the best explicit extractor in terms of supporting least-possible min-entropy, due to Li (FOCS'15), requires min-entropy (logn) <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2+δ</sup> from its O(1/δ) sources. Further, all current techniques for constructing multi-source extractors "break" below min-entropy (log n) <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup> . In fact, existing techniques do not provide even a disperser for o(log n) sources each with min-entropy (log n) <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1.99</sup> . Apart from being a natural problem, supporting logarithmic min-entropy has applications to combinatorics. A two-source disperser, let alone an extractor, for min-entropy O(log n) induces a (log, nO(1))-Ramsey graph on n vertices. Thus, constructing such dispersers would be a significant step towards constructively matching Erdös' proof for the existence of (2log n)-Ramsey graphs on n vertices. Our construction does not rely on the sophisticated primitives that were key to the substantial recent progress on multi-source extractors, such as non-malleable extractors, correlation breakers, the lightest-bin condenser, or extractors for non-oblivious bit-fixing sources, although some of these primitives can be combined with our construction so to improve the output length and the error guarantee. Instead, at the heart of our construction is a new primitive called an independence-preserving merger. The construction of the latter builds on the alternating extraction technique.
Year
DOI
Venue
2016
10.1109/FOCS.2016.27
2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS)
Keywords
DocType
Volume
extractors,independence-preserving mergers,correlation breakers
Conference
23
ISSN
ISBN
Citations 
0272-5428
978-1-5090-3934-0
8
PageRank 
References 
Authors
0.45
22
2
Name
Order
Citations
PageRank
Gil Cohen111916.43
Leonard J. Schulman21328136.88