TY - GEN
T1 - Two-source dispersers for polylogarithmic entropy and improved Ramsey graphs
AU - Cohen, Gil
N1 - Funding Information:
This work was done while the author was at the Department of Computer Science and Applied Mathematics, Weizmann Institute of Science. I wish to thank Ran Raz and Avi Wigderson for their warm encouragement. On a personal note, it is uncustomary to acknowledge one's partner in life in mathematical papers. However, given that this paper was intensively written in the last month of my wife's pregnancy and in the first month of parenthood to the newborn baby girl Meshi and to our sweet Yahli, I will allow myself to make an exception - thank you Orit! Your support and belief in my abilities are uncanny.
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 -