A Simple Explicit Construction of an $n^{\Tilde{O}(\log n)}$-Ramsey Graph

Boaz Barak

We show a simple explicit construction of an $2^{\Tilde{O}(\sqrt{\log n})}$ Ramsey graph. That is, we provide a $\poly(n)$-time algorithm to output the adjacency matrix of an undir…