Two-Source Dispersers for Polylogarithmic Entropy and Improved Ramsey Graphs

Gil Cohen

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 proo…