CaltechAUTHORS
  A Caltech Library Service

Extractors for Near Logarithmic Min-Entropy

Cohen, Gil and Schulman, Leonard J. (2016) Extractors for Near Logarithmic Min-Entropy. In: IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS). IEEE , Piscataway, NJ, pp. 178-187. ISBN 978-1-5090-3933-3. http://resolver.caltech.edu/CaltechAUTHORS:20170127-140321585

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:20170127-140321585

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)^(1+δ). 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)^(2+δ) from its O(1/δ) sources. Further, all current techniques for constructing multi-source extractors "break" below min-entropy (log n)^2. In fact, existing techniques do not provide even a disperser for o(log n) sources each with min-entropy (log n)^(1.99). 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.


Item Type:Book Section
Related URLs:
URLURL TypeDescription
http://dx.doi.org/10.1109/FOCS.2016.27 DOIArticle
http://ieeexplore.ieee.org/document/7782930/PublisherArticle
Additional Information:© 2016 IEEE.
Record Number:CaltechAUTHORS:20170127-140321585
Persistent URL:http://resolver.caltech.edu/CaltechAUTHORS:20170127-140321585
Official Citation:G. Cohen and L. J. Schulman, "Extractors for Near Logarithmic Min-Entropy," 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), New Brunswick, NJ, 2016, pp. 178-187. doi: 10.1109/FOCS.2016.27 URL: http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=7782930&isnumber=7782901
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:73784
Collection:CaltechAUTHORS
Deposited By: Tony Diaz
Deposited On:27 Jan 2017 22:22
Last Modified:27 Jan 2017 22:22

Repository Staff Only: item control page