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 -