摘要：Let G be any n-vertex graph whose random walk matrix has its nontrivialeigenvalues bounded in magnitude by 1/√∆ (for example, a random graph G of averagedegree Θ(∆) typically has this property). We show that the exp clognlog∆-round Sherali–Adams linear programming hierarchy certifies that the maximum cut in such a G is at most50.1% (in fact, at most 12 +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/loglogn) = no(1)roundssuffice.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 areneeded for effective refutation. Indeed, our results imply that constant-round Sherali–Adamscan strongly refute random Boolean k-CSP instances with nd k/2e +δconstraints; previouslythis had only been done with spectral algorithms or the SOS SDP hierarchy. We also showsimilar results for other classical combinatorial optimization problems such as independentset, max clique, and vertex cover.
