Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR15-095 | 14th June 2015 20:05

Two-Source Dispersers for Polylogarithmic Entropy and Improved Ramsey Graphs


Authors: Gil Cohen
Publication: 14th June 2015 20:15
Downloads: 2734


In his 1947 paper that inaugurated the probabilistic method, Erdös proved the existence of $2\log{n}$-Ramsey graphs on $n$ vertices. Matching Erdös' result with a constructive proof is 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 [Ann. Math'12], who constructed a $2^{2^{(\log\log{n})^{1-\alpha}}}$-Ramsey graph, for some small universal constant $\alpha > 0$.

In this work, we significantly improve the result of Barak et al. and construct $2^{(\log\log{n})^c}$-Ramsey graphs, for some universal constant $c$. In the language of theoretical computer science, our work resolves the problem of explicitly constructing two-source dispersers for polylogarithmic entropy.

ISSN 1433-8092 | Imprint