Max Cut with Small-Dimensional SDP Solutions GenAI tools were used in this paper. Our key technical lemma, Theorem 2.1 , was first proved by Google’s internal Gemini model with a weaker bound ε n 2 \varepsilon n^{2} for unspecified ε ( d ) > 0 \varepsilon(d)>0 , which was reported in [ 18 ] . Later, we used our personal subscriptions of ChatGPT 5.2 (“Extended Pro”) and Gemini 3.0 (“Pro DeepThink”) to obtain the optimal bound of ε = 2 − Θ ( d ) \varepsilon=2^{-\Theta(d)} . Its proofs are edited by the authors and appear in Section 2 .
Hsien-Chih Chang, Suprovat Ghoshal, Euiwoong Lee · 2026
Read Max Cut with Small-Dimensional SDP Solutions GenAI tools were used in this paper. Our key technical lemma, Theorem 2.1 , was first proved by Google’s internal Gemini model with a weaker bound ε n 2 \varepsilon n^{2} for unspecified ε ( d ) > 0 \varepsilon(d)>0 , which was reported in [ 18 ] . Later, we used our personal subscriptions of ChatGPT 5.2 (“Extended Pro”) and Gemini 3.0 (“Pro DeepThink”) to obtain the optimal bound of ε = 2 − Θ ( d ) \varepsilon=2^{-\Theta(d)} . Its proofs are edited by the authors and appear in Section 2 . by Hsien-Chih Chang, Suprovat Ghoshal, Euiwoong Lee (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-13971.txt.
Introduction
Chang, Ghoshal, and Lee ask whether Max-Cut rounding can beat the classic Goemans-Williamson ratio when the SDP solution lives in few dimensions. For every fixed dimension they give a fast rounding algorithm using strengthened SDP solutions. It produces cuts beating the classic ratio of about 0.88 by a dimension bonus. A fresh geometric lemma about signs of low-dimensional Gaussian draws drives the gain.
Catalog record
| CREATOR | Hsien-Chih Chang, Suprovat Ghoshal, Euiwoong Lee |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 55907 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2604.13971
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Max Cut with Small-Dimensional SDP Solutions GenAI tools were used in this paper. Our key technical lemma, Theorem 2.1 , was first proved by Google’s internal Gemini model with a weaker bound ε n 2 \varepsilon n^{2} for unspecified ε ( d ) > 0 \varepsilon(d)>0 , which was reported in [ 18 ] . Later, we used our personal subscriptions of ChatGPT 5.2 (“Extended Pro”) and Gemini 3.0 (“Pro DeepThink”) to obtain the optimal bound of ε = 2 − Θ ( d ) \varepsilon=2^{-\Theta(d)} . Its proofs are edited by the authors and appear in Section 2 . Hsien-Chih Chang, Suprovat Ghoshal, Euiwoong Lee 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 α GW ≈ 0.87856 \alpha_{\mathrm{GW}}\approx 0.87856 , it is natural to ask whether one can beat α GW \alpha_{\mathrm{GW}} when the SDP solution lives in ℝ d \mathbb{R}^{d} for a small dimension d d . We answer this in the affirmative for every fixed d d : there is a polynomial-time rounding algorithm that, given a d d -dimensional feasible solution to the standard Max-Cut SDP strengthened with triangle inequalities, produces a cut of expected value at least ( α GW + 2 − O ( d ) ) (\alpha_{\mathrm{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. 1 Introduction Max-Cut is a canonical combinatorial optimization problem of partitioning the vertex set of a weighted undirected graph G=(V,E,w) into two sides so as to maximize the total weight of edges crossing the cut. One of Karp’s 21 NP-complete problems [ 12 ] , Max-Cut has served as a testing ground for new ideas in approximation algorithms and hardness of approximation. From the algorithms side, the Goemans-Williamson (GW) algorithm [ 9 ] is one of the most well-known SDP-based approximation algorithms. It solves the basic semidefinite relaxation \max\ \ \frac{1}{2}\sum_{(i,j)\in E}w_{ij}\bigl(1-\langle v_{i},v_{j}\rangle\bigr)\qquad\text{s.t. }\|v_{i}\|_{2}=1\text{ for all }i\in V, (1) and rounds a feasible solution by sampling a random hyperplane through the origin and cutting according to the induced signs: sample g\sim\mathcal{N}(0,I) and output x_{i}=\mathrm{sgn}(\langle g,v_{i}\rangle) . For an edge (i,j) , the cut probability is \Pr[x_{i}\neq x_{j}]=\arccos(\langle v_{i},v_{j}\rangle)/\pi , and the worst-case ratio between this probability and the SDP contribution (1-\langle v_{i},v_{j}\rangle)/2 is the famous Goemans-Williamson constant \alpha_{\mathrm{GW}}\ :=\ \min_{\rho\in[-1,1]}\frac{\arccos(\rho)/\pi}{(1-\rho)/2}\ \approx\ 0.87856, which shows that this algorithms is an \alpha_{GW} -approximation. Moreover, assuming the Unique Games Conjecture [ 14 ] , no polynomial-time algorithm can achieve a (\alpha_{\mathrm{GW}}+\varepsilon) -approximation for any constant \varepsilon>0 [ 13 ] . Thus, improving upon \alpha_{\mathrm{GW}} in the worst case is believed impossible. Under what conditions could we improve the \alpha_{GW} -approximation by a constant? There have been active studies on this question, mainly relying on structural assumptions on the graph G , including when G is dense (i.e., |E|=\Omega(n) ) [ 1 ] or low-degree (i.e., the maximum degree is O(1) ) [ 6 , 10 ] . Low-dimensional SDP solutions. In this paper, we study the low-dimensionality assumption: the optimal (or near-optimal) SDP solution happens to admit a realization in \mathbb{R}^{d} for small d . It departs from previous results in that we pose structural assumptions on the SDP solution rather than the graph. Avidor and Zwick [ 2 ] initiated the systematic study of this topic. They showed that in two dimensions, one can achieve the ratio \frac{32}{25+5\sqrt{5}}\approx 0.884458 (originally obtained by Goemans in unpublished work), and in three dimensions they designed the “yin–yang” rounding procedure with ratio about 0.8818 . This resolves in the negative a question of Feige and Schechtman [ 7 ] asking whether one can have integrality ratios arbitrarily close to \alpha_{\mathrm{GW}} while admitting a three-dimensional optimal embedding. Avidor and Zwick conjectured that for every fixed d there is a rounding algorithm beating \alpha_{\mathrm{GW}} on instances whose optimal SDP solution lies in \mathbb{R}^{d} . The conjecture is stated with respect to the basic SDP ( 1 ), but they also asked whether the same conclusion can be made with respect to the SDP with the following triangle inequality constraints . \|a_{i}v_{i}-a_{j}v_{j}\|_{2}^{2}+\|a_{j}v_{j}-a_{k}v_{k}\|_{2}^{2}\ \geq\ \|a_{i}v_{i}-a_{k}v_{k}\|_{2}^{2}\quad\mbox{ for every }i,j,k\in V\mbox{ and }a_{i},a_{j},a_{k}\in\{\pm 1\}, Prior to this work, no such improvement was known beyond d=2,3 with or without the triangle inequalities. The lack of progress on this conjecture is somewhat surprising, given that the positive answer has been known for the related Grothendieck problems. In the (bipartite) Grothendieck problem, given A\in\mathbb{R}^{m\times n} , the goal is to compute x\in\{\pm 1\}^{m} and y\in\{\pm 1\}^{n} to maximize x^{T}Ay . In the PSD Grothendieck problem, given positive semidefinite A\in\mathbb{R}^{n\times n} , the goal is to compute x\in\{\pm 1\}^{n} to maximize x^{T}Ax . The optimal approximation ratios for these problems, assuming the UGC, are the Grothendieck constant K_{G} and \pi/2 respectively [ 15 , 5 ] , but for both problems, bounded-dimension SDP solutions can be rounded with a strictly better approximation ratio [ 3 , 4 ] . Our result. We give a positive answer to the question of Avidor and Zwick with the triangle inequalities, albeit with an exponentially small improvement. Theorem 1.1 (Main Theorem) There exists a randomized polynomial-time algorithm with the following guarantee. Given a feasible d -dimensional solution \{v_{i}\in\mathbb{R}^{d}:\|v_{i}\|_{2}=1\}_{i\in V} to the Max-Cut SDP strengthened with triangle inequalities, the algorithm outputs a cut x\in\{\pm 1\}^{V} whose expected value is at least \bigl(\alpha_{\mathrm{GW}}+2^{-O(d)}\bigr)\cdot\mathrm{SDP}, where \mathrm{SDP} is the objective value of the input solution. The algorithm is a local-improvement post-processing of GW rounding, following the framework of Feige–Karpinski–Langberg [ 6 ] and its sharpened analysis by Hsieh–Kothari [ 10 ] for Max-Cut with the bounded (maximum) degree. Our contribution is a new geometric theorem for low-dimensional Gaussian signs, which lets us replace the dependence on the (possibly unbounded) graph degree by an explicit dependence on the SDP dimension. Finally, we also mention that our proof directly extends to the weaker local dimension condition on the SDP solution \{v_{i}\}_{i\in V} : for every i\in V , the vectors of its neighbors (i.e., \{v_{j}:(j,i)\in E\} ) lie in a d -dimensional subspace. In particular, our result holds for any graphs with maximum degree d as well, though our improvement of 2^{-O(d)} over \alpha_{GW} is much worse than the 1/\widetilde{\Omega}(d^{2}) via the direct analysis [ 10 ] . 1.1 Technical overview The proof of Theorem 1.1 decomposes into a geometric statement and its algorithmic application. 1. A geometric anti-concentration theorem. Let v_{1},\dots,v_{n} be unit vectors in \mathbb{R}^{d} such that \langle v_{i},v_{j}\rangle\geq-0.9 for all i\neq j . Sample a random Gaussian vector g\sim\mathcal{N}(0,I_{d}) and define X_{i}=\mathrm{sgn}(\langle g,v_{i}\rangle)\in\{\pm 1\} and X=\sum_{i=1}^{n}X_{i} . Our main geometric theorem (proved in Section 2 ) shows that \mathbb{E}[X^{2}]\ \geq\ n^{2}\cdot 2^{-O(d)}. In other words, the random hyperplane induced by g produces a nontrivial imbalance on the vectors \{v_{i}\} . We present three self-contained proofs, each emphasizing a different viewpoint (tensor moments, Gaussian/Hermite analysis, and positive-definite kernels on the sphere). 2. From geometry to an improved Max-Cut rounding. Given the geometric theorem, our algorithm follows the framework of Feige–Karpinski–Langberg [ 6 ] . After performing the standard hyperplane rounding algorithm (i.e., sampling