Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR16-014 | 3rd February 2016 03:02

Extractors for Near Logarithmic Min-Entropy


Authors: Gil Cohen, Leonard Schulman
Publication: 3rd February 2016 03:12
Downloads: 821


The main contribution of this work is an explicit construction of extractors for near logarithmic min-entropy. For any $\delta > 0$ we construct an extractor for $O(1/\delta)$ $n$-bit sources with min-entropy $(\log{n})^{1+\delta}$. This is most interesting when $\delta$ is set to a small constant, though the result also yields an extractor for $O(\log\log{n})$ 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 $(\log{n})^{2+\delta}$ from its $O(1/\delta)$ 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{n})^{O(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 $(2\log{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.

ISSN 1433-8092 | Imprint