Revised: October 29, 2020

Published: September 28, 2021

**Keywords:**hierarchies, Sherali--Adams, combinatorial optimization

**Categories:**complexity theory, hierarchies, Sherali--Adams, combinatorial optimization, CCC, CCC 2019 special issue

**ACM Classification:**G.1.6

**AMS Classification:**03F20, 68W25

**Abstract:**
[Plain Text Version]

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 $\exp\left(c \frac{\log n}{\log \Delta}\right)$-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 MAX-CUT 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. We also show similar results for other classical combinatorial optimization problems such as independent set, max clique, and vertex cover.

----------------

A conference version of this paper appeared in the Proceedings of the 34th Computational Complexity Conference (CCC'19).