2018/12/24 by O'Donnell, Ryan, Schramm, Tselil · 1 citation
#Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.1812.09967
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 exp(c (log n)/(log Δ))-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-Ω(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 n\lceil k/2 \rceil + δ constraints; previously this had only been done with spectral algorithms or the SOS SDP hierarchy.