Revised: October 29, 2020
Published: September 28, 2021
Abstract: [Plain Text Version]
Let $G$ be any $n$-vertex graph whose random walk matrix has its nontrivial eigenvalues bounded in magnitude by 1ドル/\sqrt{\Delta}$ (for example, a random graph $G$ of average degree $\Theta(\Delta)$ typically has this property). We show that the $\exp\left(c \frac{\log n}{\log \Delta}\right)$-round Sherali--Adams linear programming hierarchy certifies that the maximum cut in such a $G$ is at most 50ドル.1\%$ (in fact, at most $\tfrac12 + 2^{-\Omega(c)}$). For example, in random graphs with $n^{1.01}$ edges, $O(1)$ rounds suffice; in random graphs with $n \cdot \text{polylog(n)}$ edges, $n^{O(1/\log \log n)} = n^{o(1)}$ rounds suffice. Our results stand in contrast to the conventional beliefs that linear programming hierarchies perform poorly for MAX-CUT and other CSPs, and that eigenvalue/SDP methods are needed for effective refutation. Indeed, our results imply that constant-round Sherali--Adams can strongly refute random Boolean $k$-CSP instances with $n^{\lceil k/2 \rceil + \delta}$ constraints; previously this had only been done with spectral algorithms or the SOS SDP hierarchy. We also show similar results for other classical combinatorial optimization problems such as independent set, max clique, and vertex cover.
----------------
A conference version of this paper appeared in the Proceedings of the 34th Computational Complexity Conference (CCC'19).