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.

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 -