Sherali--Adams Strikes Back

Let G be any n-vertex graph whose random walk matrix has its nontrivial eigenvalues bounded in magnitude by 1/√Delta (for example, a random graph G of average degree~Theta(Delta) typically has this property). We show that the expBig(c fraclog nlog DeltaBig)-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 n1.01 edges, O(1) rounds suffice; in random graphs with n · polylog(n) edges, nO(1/log log n) = no(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 nlceil k/2 rceil + δ constraints; previously this had only been done with spectral algorithms or the SOS SDP hierarchy.