Two-Source Dispersers for Polylogarithmic Entropy and Improved Ramsey Graphs

by Gil Cohen

Oded's comments

I care about the ``language of theoretical computer science'' (or rather its own problems): This work improves the min-entropy bound for which two-source $n$-bit long dispersers can be constructed from $\exp(\log^{1-\Omega(1)} n)=n^{1/\log^{\Omega(1)}n}$ to $\poly(\log n)$.

The original abstract (slightly revised)

In his 1947 paper that inaugurated the probabilistic method, Erdos proved the existence of $2\log{N}$-Ramsey graphs on $N$ vertices. Matching Erdos's result with a constructive proof is a central problem in combinatorics, which 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 min-entropy.

See ECCC TR15-095.

Back to list of Oded's choices.