Subexponential LPs Approximate Max-Cut

We show that for every $\varepsilon > 0$ , the degree $-n^{\varepsilon}$ Sherali-Adams linear program (with $\exp(\tilde{O}(n^{\varepsilon})$ ) variables and constraints) approximates the maximum cut problem within a factor of ( $\frac{1}{2}+\varepsilon^{\prime}$ ), for some $\varepsilon^{\prime}(\varepsilon) > 0$ . Our result provides a surprising converse to known lower bounds against all linear programming relaxations of Max-Cut [1], [2], and hence resolves the extension complexity of approximate Max-Cut for approximation factors close to $\frac{1}{2}$ (up to the function $\varepsilon^{\prime}(\varepsilon)$ ). Previously, only semidefinite programs and spectral methods were known to yield approximation factors better than $\frac{1}{2}$ for Max-Cut in time $2^{o(n)}$ . We also show that constant-degree Sherali-Adams linear programs (with $\text{poly}(n)$ variables and constraints) can solve Max-Cut with approximation factor close to 1 on graphs of small threshold rank: this is the first connection of which we are aware between threshold rank and linear programming-based algorithms. Our results separate the power of Sherali-Adams versus Lovasz-Schrijver hierarchies for approximating Max-Cut, since it is known [3] that ( $\frac{1}{2}+\varepsilon$ ) approximation of Max Cut requires $\Omega_{\varepsilon}(n)$ rounds in the Lovasz-Schrijver hierarchy. We also provide a subexponential time approximation for Khot's Unique Games problem [4]: we show that for every $\varepsilon > 0$ the degree-( $n^{\varepsilon}\log q$ ) Sherali-Adams linear program distinguishes instances of Unique Games of value $\geq 1-\varepsilon ^{\prime}$ from instances of value $\leq \varepsilon^{\prime}$ , for some $\varepsilon^{\prime}(\varepsilon) > 0$ , where $q$ is the alphabet size. Such guarantees are qualitatively similar to those of previous subexponential-time algorithms for Unique Games but our algorithm does not rely on semidefinite programming or subspace enumeration techniques [5]–[7].