Max Cut with Small-Dimensional SDP Solutions

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 ${\alpha }_{GW}\approx 0.87856$, it is natural to ask whether one can beat ${\alpha }_{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 $({\alpha }_{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.