Theory of Computing ------------------- Title : Sherali--Adams Strikes Back Authors : Ryan O'Donnell and Tselil Schramm Volume : 17 Number : 9 Pages : 1-30 URL : https://theoryofcomputing.org/articles/v017a009 Abstract -------- 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(c\frac{\log n}{\log \Delta})$-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 . 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.