Extractors for Near Logarithmic Min-Entropy
Extractors for Near Logarithmic Min-Entropy
复制标题
近对数最小熵提取器
DOI：
10.1109/focs.2016.27
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
L. Schulman
中科院分区：
文献类型：
--
作者：
Gil Cohen;L. Schulman
这项工作的主要贡献是显式地构造了近对数最小熵的抽取子。对于任意δ>；0，我们构造了一个最小熵(δ)1+δ的O(1/logn)n比特信源的抽取器。当δ被设置为一个较小的常量时，这是最有趣的，尽管结果也为O(LoglogN)源生成了一个具有对数最小熵的提取器。在这项工作之前，由于Li(FOCS‘15)，就支持最小可能最小熵而言，最好的显式抽取器需要来自O(1/δ)源的最小熵(LogN)2+δ。此外，当前用于构造多源抽取器的所有技术都低于最小熵(Logn)2。事实上，现有技术甚至没有为每个具有最小熵(Logn)1.99的o(Logn)源提供分散器。除了是一个自然问题，支持对数最小熵在组合学中也有应用。最小熵O(Logn)的双源分散子，更不用说抽取子，可以得到n个顶点上的(log，no(1))-Ramsey图。因此，构造这样的离散子将是朝着建设性地匹配ErdöS关于n个顶点上存在(2logn)-Ramsey图的证明的重要一步。我们的构造不依赖于复杂的基元，这些基元是多源萃取器最近取得实质性进展的关键，例如不可延展的萃取器、相关断路器、最轻的箱电容器或用于非遗忘比特固定源的萃取器，尽管这些基元中的一些可以与我们的构造相结合，从而提高输出长度和误差保证。相反，我们建设的核心是一种新的原语，称为保持独立的合并。后者的构建建立在交替提取技术的基础上。
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.
影响因子：
4.9
作者：
Chattopadhyay, Eshan;Zuckerman, David
通讯作者：
Zuckerman, David