Subexponential LPs Approximate Max-Cut

Samuel B. Hopkins, Tselil Schramm, Luca Trevisan

We show that for every $\epsilon >0$, the degree-$n^{\epsilon }$ Sherali-Adams linear program (with $\exp (\tilde{O}(n^{\epsilon }))$ variables and constraints) approximates the…