# Sherali--Adams Strikes Back

arXiv: https://arxiv.org/abs/1812.09967 · HTML: https://mlsanity.com/paper/1812.09967/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 24 Dec 2018.

## Built on by (most cited first, 1 of 1)

- [An Information-Minimal Geometry for Qubit-Efficient Optimization](https://mlsanity.com/paper/2511.08362/) (2025)

## Abstract (arXiv)

Let G be any n-vertex graph whose random walk matrix has its nontrivial eigenvalues bounded in magnitude by 1/√Delta (for example, a random graph G of average degree~Theta(Delta) typically has this property). We show that the expBig(c fraclog nlog DeltaBig)-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 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 nlceil k/2 rceil + δ constraints; previously this had only been done with spectral algorithms or the SOS SDP hierarchy.