Abstract
Conventional wisdom asserts that linear programs (LPs) perform poorly for max-cut and other constraint satisfaction problems, and that semidefinite programming and spectral methods are needed to give nontrivial bounds. In this talk, I will describe a recent result that stands in contrast to this wisdom: we show that surprisingly small LPs can give nontrivial upper bounds for constraint satisfaction problems. Even more surprisingly, the quality of our bounds depends on the spectral radius of the adjacency matrix of the associated graph. For example, in a random $\Delta$-regular $n$-vertex graph, the $\exp(c \frac{\log n}{\log \Delta})$-round Sherali--Adams LP certifies that the max cut has value at most $50.1\%$. In random graphs with $n^{1.01}$ edges, $O(1)$ rounds suffice; in random graphs with $n \cdot \log(n)$ edges, $n^{O(1/\log \log n)} = n^{o(1)}$ rounds suffice.