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 $expBig(c frac{log n}{log Delta}Big)$-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 maxcut 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.
Download