Sherali--Adams Strikes Back
share
Let G be any n-vertex graph whose random walk matrix has its nontrivial eigenvalues bounded in magnitude by 1/√(Δ) (for example, a random graph G of average degree Θ(Δ) typically has this property). We show that the (c n/Δ)-round Sherali--Adams linear programming hierarchy certifies that the maximum cut in such a G is at most 50.1% (in fact, at most 12 + 2^-Ω(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/ n) = n^o(1) rounds suffice. Our results stand in contrast to the conventional beliefs that linear programming hierarchies perform poorly for 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^ k/2 + δ constraints; previously this had only been done with spectral algorithms or the SOS SDP hierarchy.
READ FULL TEXT