An efficient reduction from two-source to non-malleable extractors: achieving near-logarithmic min-entropy
An efficient reduction from two-source to non-malleable extractors: achieving near-logarithmic min-entropy
复制标题
从双源提取器到不可延展提取器的有效减少：实现接近对数的最小熵
DOI：
10.1145/3055399.3055423
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
A. Ta
中科院分区：
文献类型：
--
作者：
Avraham Ben;Dean Doron;A. Ta
Chattopadhyay和Zuckerman（2016）的突破性结果给出了从显式双源提取器的构造到显式不可延展提取器的构造的简化。然而，即使假设存在最佳显式不可延展提取器，也只能给出poly（logn）熵的两个源提取器（或Ramsey图），而不是最佳O（logn）。在本文中，我们修改的建设，以解决上述障碍。使用目前最好的显式非延展性提取器，我们得到了一个显式的二部Ramsey图的大小为2k的集合，k=O（logn logloglogn）。对非延展性提取器结构的任何进一步改进将立即产生相应的双源提取器。直觉上，Chattopadhyay和Zuckerman使用提取器作为采样器，我们观察到可以使用较弱的对象-一个具有小熵隙和非常短种子的某处随机冷凝器。我们还展示了如何使用Raz，Reingold和Vadhan（1999）的误差减少技术以及Zuckerman（2006）的常度分散器来显式地构造这个较弱的对象，这些方法也适用于极小的测试。
The breakthrough result of Chattopadhyay and Zuckerman (2016) gives a reduction from the construction of explicit two-source extractors to the construction of explicit non-malleable extractors. However, even assuming the existence of optimal explicit non-malleable extractors only gives a two-source extractor (or a Ramsey graph) for poly(logn) entropy, rather than the optimal O(logn). In this paper we modify the construction to solve the above barrier. Using the currently best explicit non-malleable extractors we get an explicit bipartite Ramsey graphs for sets of size 2k, for k=O(logn loglogn). Any further improvement in the construction of non-malleable extractors would immediately yield a corresponding two-source extractor. Intuitively, Chattopadhyay and Zuckerman use an extractor as a sampler, and we observe that one could use a weaker object - a somewhere-random condenser with a small entropy gap and a very short seed. We also show how to explicitly construct this weaker object using the error reduction technique of Raz, Reingold and Vadhan (1999), and the constant-degree dispersers of Zuckerman (2006) that also work against extremely small tests.
影响因子：
4.9
作者：
Chattopadhyay, Eshan;Zuckerman, David
通讯作者：
Zuckerman, David