Max Cut with Small-Dimensional SDP Solutions
Pith reviewed 2026-05-10 12:04 UTC · model grok-4.3
The pith
For any fixed dimension d there is a polynomial-time rounding algorithm that turns a d-dimensional feasible solution to the triangle-inequality strengthened Max-Cut SDP into a cut whose expected value is at least (alpha_GW + 2 to the minus
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
The authors prove that, given any feasible d-dimensional solution to the Max-Cut SDP strengthened with triangle inequalities, there exists a polynomial-time rounding algorithm producing a random cut whose expected value is at least (alpha_GW + 2^{-O(d)}) times the SDP value. The proof centers on a geometric anti-concentration lemma that bounds how often low-dimensional Gaussian projections can produce sign patterns too aligned with the SDP vectors, thereby allowing the algorithm to avoid the worst-case behavior of plain hyperplane rounding.
What carries the argument
A new geometric anti-concentration lemma for the signs of low-dimensional Gaussian projections, which supplies quantitative control on the distribution of random hyperplane cuts when the SDP vectors span only d dimensions.
If this is right
- The approximation ratio for Max-Cut improves beyond alpha_GW on every instance whose optimal SDP solution is realizable in dimension d.
- The additive improvement term 2^{-O(d)} quantifies the dimensional advantage and becomes negligible only when d grows.
- The result requires the SDP to be strengthened with triangle inequalities; without them the same guarantee need not hold.
- The algorithm runs in polynomial time for each fixed d, preserving tractability while gaining the dimensional boost.
Where Pith is reading between the lines
- Worst-case integrality-gap examples for Max-Cut must require high-dimensional SDP solutions.
- Projecting an arbitrary SDP solution onto a low-dimensional subspace before rounding might yield practical gains even when the original solution is high-dimensional.
- The same anti-concentration technique could be tested on other vector-rounding problems such as Max-2-SAT or Grothendieck.
- It is open whether the improvement can be made independent of the triangle inequalities or whether the exponential dependence on d can be improved.
Load-bearing premise
The given SDP solution admits a realization by vectors in Euclidean space of dimension d, and the stated geometric anti-concentration bound on low-dimensional Gaussian sign patterns holds.
What would settle it
A concrete d-dimensional vector assignment satisfying the SDP constraints and all triangle inequalities for which no rounding procedure (even randomized) can achieve expected cut value larger than alpha_GW times the SDP value, or an explicit low-dimensional Gaussian distribution that violates the claimed anti-concentration bound on sign patterns.
read the original 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 $\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.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The manuscript claims that for every fixed dimension d, there exists a polynomial-time rounding algorithm which, given a d-dimensional feasible solution to the Max-Cut SDP strengthened by triangle inequalities, returns a cut whose expected value is at least (α_GW + 2^{-O(d)}) times the SDP value. The improvement over the Goemans-Williamson ratio is obtained by invoking a new geometric anti-concentration lemma on the sign patterns of low-dimensional Gaussian projections.
Significance. If the central lemma holds with the stated quantitative bound, the result is significant: it supplies the first explicit additive improvement over α_GW that is parameterized by the dimension of the SDP solution. The new anti-concentration lemma itself constitutes a technical contribution that may be reusable in other rounding analyses. The paper gives a concrete, dimension-dependent rate rather than an existential statement, which strengthens its utility for understanding low-rank integrality gaps.
major comments (3)
- [Lemma 3.2] Lemma 3.2 (anti-concentration statement): the claimed 2^{-O(d)} probability bound is derived under the assumption that the Gram matrix satisfies the triangle inequalities; the proof must explicitly verify that these inequalities imply the minimum angular separation or general-position condition required for the quantitative anti-concentration to hold. If the lemma tacitly needs a stricter geometric hypothesis not enforced by the SDP, the additive improvement collapses for some feasible solutions.
- [Section 5, Theorem 5.1] Section 5, rounding analysis (Theorem 5.1): the integration of the new lemma into the Goemans-Williamson hyperplane-rounding expectation produces an additive 2^{-O(d)} term, but the error terms arising from the low-dimensional projection and from the triangle-inequality enforcement are not bounded explicitly; it is possible that these errors are Ω(2^{-c d}) for c<1 and thereby cancel the claimed improvement for moderate d.
- [Section 4] Section 4, algorithmic description: the procedure is asserted to run in polynomial time for fixed d, yet the analysis does not state the precise dependence on d (e.g., whether an enumeration over sign patterns or a sampling routine incurs 2^{O(d)} factors that would make the algorithm exponential in d).
minor comments (2)
- [Introduction] The notation distinguishing the SDP value, the expected cut value, and the random cut value should be introduced consistently in the introduction and used uniformly thereafter.
- [Figure 1] Figure 1 (schematic of the rounding) would benefit from an explicit label indicating which step invokes the new anti-concentration lemma.
Simulated Author's Rebuttal
We thank the referee for the careful and constructive review. The positive assessment of the result's significance is appreciated. We respond point-by-point to the major comments below, indicating where revisions will be made to strengthen the manuscript.
read point-by-point responses
-
Referee: [Lemma 3.2] Lemma 3.2 (anti-concentration statement): the claimed 2^{-O(d)} probability bound is derived under the assumption that the Gram matrix satisfies the triangle inequalities; the proof must explicitly verify that these inequalities imply the minimum angular separation or general-position condition required for the quantitative anti-concentration to hold. If the lemma tacitly needs a stricter geometric hypothesis not enforced by the SDP, the additive improvement collapses for some feasible solutions.
Authors: We agree that the connection between the triangle inequalities and the geometric conditions for anti-concentration should be made fully explicit. The current proof of Lemma 3.2 invokes the triangle inequalities to bound the inner products and thereby obtain a minimum angular separation of order 2^{-O(d)} between distinct vectors; this separation is then used to control the probability of degenerate sign patterns under Gaussian projection. In the revised manuscript we will insert a short auxiliary claim (immediately preceding the anti-concentration argument) that derives the required separation directly from the triangle inequalities and verifies that it is sufficient for the quantitative bound stated in the lemma. This change removes any ambiguity about the hypothesis under which the lemma applies to feasible SDP solutions. revision: yes
-
Referee: [Section 5, Theorem 5.1] Section 5, rounding analysis (Theorem 5.1): the integration of the new lemma into the Goemans-Williamson hyperplane-rounding expectation produces an additive 2^{-O(d)} term, but the error terms arising from the low-dimensional projection and from the triangle-inequality enforcement are not bounded explicitly; it is possible that these errors are Ω(2^{-c d}) for c<1 and thereby cancel the claimed improvement for moderate d.
Authors: The referee correctly identifies that the proof of Theorem 5.1 absorbs several error terms into the 2^{-O(d)} notation without displaying their precise exponents. In the revised version we will expand the expectation calculation to isolate three sources of error: (i) the discrepancy between the original SDP vectors and their low-dimensional projections, (ii) the additive loss incurred when enforcing the triangle inequalities during rounding, and (iii) the tail probability from the anti-concentration lemma itself. We will show that each of these terms is at most 2^{-c d} for an explicit c > 1 that is strictly larger than the constant hidden in the main anti-concentration gain, thereby guaranteeing that the net additive improvement remains positive for every fixed d. The updated proof will include a short lemma collecting the explicit constants. revision: yes
-
Referee: [Section 4] Section 4, algorithmic description: the procedure is asserted to run in polynomial time for fixed d, yet the analysis does not state the precise dependence on d (e.g., whether an enumeration over sign patterns or a sampling routine incurs 2^{O(d)} factors that would make the algorithm exponential in d).
Authors: The algorithm of Section 4 enumerates a constant (for fixed d) number of candidate sign patterns arising from the low-dimensional geometry and then solves a small linear program for each pattern; the enumeration therefore contributes a factor of 2^{O(d)}. Because d is treated as a fixed constant, the overall running time remains polynomial in the input size n. Nevertheless, we accept that an explicit statement of the d-dependence improves clarity. In the revision we will add a sentence in Section 4 stating that the running time is O(n^3 · 2^{O(d)}), which is polynomial for every fixed d while making the exponential dependence on d transparent. revision: yes
Circularity Check
No circularity; new lemma provides independent improvement
full rationale
The derivation introduces an explicitly new geometric anti-concentration lemma for signs of low-dimensional Gaussian projections and applies it to obtain the additive 2^{-O(d)} improvement over α_GW for d-dimensional SDP solutions (strengthened only by triangle inequalities). No step reduces by construction to a fitted parameter, self-definition, or load-bearing self-citation; the central claim rests on a fresh quantitative lemma whose hypotheses are stated to follow from the low-dimensional realization and triangle inequalities, with the proof independent of the target ratio. The result is therefore self-contained against external benchmarks.
Axiom & Free-Parameter Ledger
axioms (1)
- ad hoc to paper Existence and correctness of a new geometric anti-concentration lemma for signs of low-dimensional Gaussian projections
Reference graph
Works this paper leans on
-
[1]
Polynomial time approximation schemes for dense instances of np-hard problems
[AKK95] Sanjeev Arora, David Karger, and Marek Karpinski. Polynomial time approximation schemes for dense instances of np-hard problems. InProceedings of the twenty-seventh annual ACM symposium on Theory of computing, pages 284–293, 1995. [AZ05] Adi Avidor and Uri Zwick. Rounding two and three dimensional solutions of the SDP relaxation of MAX CUT. InAppr...
work page 1995
-
[2]
Automata, Languages, and Programming (ICALP), Leibniz International Proceedings in Informatics (LIPIcs), 2023. [Hua92] Xiaoming Huang. An extremal property for chebyshev polynomials.Journal of ap- proximation theory, 71(2):138–144, 1992. [Kar09] Richard M Karp. Reducibility among combinatorial problems. In50 Years of Integer Programming 1958-2008: from th...
work page 2023
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.