Theory of Computing
-------------------
Title     : Sherali--Adams Strikes Back
Authors   : Ryan O'Donnell and Tselil Schramm
Volume    : 17
Number    : 9
Pages     : 1-30
URL       : https://theoryofcomputing.org/articles/v017a009

Abstract
--------
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(c\frac{\log n}{\log \Delta})$-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 . 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.