TY - GEN
T1 - Two-source dispersers for polylogarithmic entropy and improved Ramsey graphs
AU - Cohen, Gil
N1 - Publisher Copyright:
© 2016 ACM.
PY - 2016/6/19
Y1 - 2016/6/19
N2 - In his influential 1947 paper that inaugurated the probabilistic method, Erdos proved the existence of 2 log n-Ramsey graphs on n vertices. Matching Erdos' 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(log log n)1-α-Ramsey graph, for some small universal constant α > 0. In this work, we significantly improve this result and construct 2(log logn)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 polylog(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).
AB - In his influential 1947 paper that inaugurated the probabilistic method, Erdos proved the existence of 2 log n-Ramsey graphs on n vertices. Matching Erdos' 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(log log n)1-α-Ramsey graph, for some small universal constant α > 0. In this work, we significantly improve this result and construct 2(log logn)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 polylog(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).
KW - Explicit constructions
KW - Ramsey graphs
KW - Zero-error dispersers
UR - http://www.scopus.com/inward/record.url?scp=84979256225&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84979256225&partnerID=8YFLogxK
U2 - 10.1145/2897518.2897530
DO - 10.1145/2897518.2897530
M3 - Conference contribution
AN - SCOPUS:84979256225
T3 - Proceedings of the Annual ACM Symposium on Theory of Computing
SP - 278
EP - 284
BT - STOC 2016 - Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing
A2 - Mansour, Yishay
A2 - Wichs, Daniel
PB - Association for Computing Machinery
T2 - 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016
Y2 - 19 June 2016 through 21 June 2016
ER -