Two-source dispersers for polylogarithmic entropy and improved ramsey graphs
Two-source dispersers for polylogarithmic entropy and improved ramsey graphs
复制标题
用于多对数熵和改进拉姆齐图的双源分散器
DOI：
10.1145/2897518.2897530
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
Gil Cohen
中科院分区：
文献类型：
--
作者：
Gil Cohen
在他的1947年有影响力的论文中，Erdős证明了在N顶点上存在2logn-ramsey图，这与结构性证明相匹配是组合学中的核心问题，这在文献中引起了重大关注。最先进的结果是在Barak，Rao，Shaltiel和Wigderson的著名论文中获得的，他们构建了22（Loglogn）1-α-Ramsey图，用于一些小的通用常数α> 0。在这项工作中，我们在理论计算机科学的语言中显着改善了这一结果，并构造了2（loglogn）c-ramsey图。对于带有熵的两个n位源（N），我们的分散器是零错误的分散器，在此工作之前输出恒定的分数。熵ω（n）。
In his influential 1947 paper that inaugurated the probabilistic method, Erdős proved the existence of 2logn-Ramsey graphs on n vertices. Matching Erdős’ result with a constructive proof is considered a central problem in combinatorics, that has gained a significant attention in the literature. The state of the art result was obtained in the celebrated paper by Barak, Rao, Shaltiel, and Wigderson who constructed a 22(loglogn)1−α-Ramsey graph, for some small universal constant α > 0. In this work, we significantly improve this result and construct 2(loglogn)c-Ramsey graphs, for some universal constant c. In the language of theoretical computer science, this resolves the problem of explicitly constructing dispersers for two n-bit sources with entropy (n). In fact, our disperser is a zero-error disperser that outputs a constant fraction of the entropy. Prior to this work, such dispersers could only support entropy Ω(n).
影响因子：
4.9
作者：
Chattopadhyay, Eshan;Zuckerman, David
通讯作者：
Zuckerman, David