Max Cut with Small-Dimensional SDP Solutions

Abstract

We study the Max-Cut semidefinite programming (SDP) relaxation in the regime where a near-optimal solution admits a low-dimensional realization. While the Goemans--Williamson hyperplane rounding achieves the worst-case optimal approximation ratio $\hat{I}{\pm }_{GW}\approx 0.87856$, it is natural to ask whether one can beat $\hat{I}{\pm }_{GW}$ when the SDP solution lives in ${\mathbb{R}}^d$ for a small dimension $d$. We answer this in the affirmative for every fixed $d$: there is a polynomial-time rounding algorithm that, given a $d$-dimensional feasible solution to the standard Max-Cut SDP strengthened with triangle inequalities, produces a cut of expected value at least $(\hat{I}{\pm }_{GW}+2^{-O(d)})$ times the SDP value. Our improvement is driven by a new geometric anti-concentration lemma for signs of low-dimensional Gaussian projections.

24 Pages