## 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.