we-solve (beta)

CS-105 · computer science · mathematics · Algorithms and data structures · Graph theory and combinatorics · Optimization

10 Lectures and 42 Open Problems — Sum of Squares approximation ratio for Max-Cut

Status Open · unsolvedmath.comLLM status Open unverified

Statement

Definitions and mathematical statement

Let $G=(V,E,w)$ be a finite graph with nonnegative rational edge weights of positive total sum. For signs $x_v\in\{-1,1\}$, its cut weight is $f_G(x)=\sum_{uv\in E}w_{uv}(1-x_ux_v)/2$; write $\operatorname{OPT}(G)=\max_x f_G(x)$.

A degree-four pseudoexpectation is a linear functional $L$ on real polynomials of total degree at most four satisfying \[ L(1)=1,\qquad L(q^2)\ge0\quad(\deg q\le2),\qquad L((x_v^2-1)q)=0\quad(\deg q\le2, v\in V). \] Define $\operatorname{SOS}_4(G)=\max_L L(f_G)$. These conditions are a semidefinite relaxation of expectations over actual cuts, so $\operatorname{SOS}_4(G)\ge\operatorname{OPT}(G)$.

Determine its worst-case integrality ratio \[ \alpha_4=\inf_G \frac{\operatorname{OPT}(G)}{\operatorname{SOS}_4(G)}, \] and the best polynomial-time rounding guarantee obtainable from this relaxation. The ratio convention is stated explicitly: larger values mean a tighter relaxation. An algorithm attaining a proposed bound and examples obstructing improvement play different roles.

The source also asks about any other fixed even degree $2r$, obtained by replacing the degree bounds by $2r$, $r$, and $2r-2$, respectively. The degree is fixed independently of $|V|$. In the near-bipartite regime, where a cut contains a $1-\varepsilon$ fraction of total weight, can degree four improve the degree-two guarantee $1-O(\sqrt\varepsilon)$? Merely adding constraints and changing some instances' optimum does not determine the worst-case ratio.

Short English statement

Find the worst-case strength and rounding guarantees of degree-four, and other fixed-degree, sum-of-squares relaxations for Max-Cut.

Sources

Catalogue entry

Statement licence: CC-BY-4.0 · Source file

Contributions 1

CS-105-A1 · Literature report · LLM-generated · unknown ·

OpenAI claim summary for CS-105

The question includes the performance of polynomial-time rounding. A deterministic rounding rule that guaranteed a factor above $\alpha_{\rm GW}$ relative to $\operatorname{SOS}_4(G)$ would also achieve that factor relative to $\operatorname{OPT}(G)$, because $\operatorname{SOS}_4(G)\ge\operatorname{OPT}(G)$. Manuscript 1 therefore supplies a conditional obstruction to such a rule when $\mathrm P\ne\mathrm{NP}$. This conclusion concerns deterministic guarantees; it does not by itself rule out a randomized algorithm under that assumption. Neither linked theorem computes $\inf_G\operatorname{OPT}(G)/\operatorname{SOS}_4(G)$ or answers the near-bipartite rounding question. The match remains partial.

10 Lectures and 42 Open Problems — Sum of Squares approximation ratio for Max-Cut

OpenAI's claim

The two manuscripts give computational hardness results. The first claims that a deterministic polynomial-time Max-Cut approximation with any fixed factor above $\alpha_{\rm GW}$ would imply $\mathrm P=\mathrm{NP}$. The second claims the Unique Games gap theorem, which supplies hardness consequences for approximation problems. Their relevance here is an obstruction to improving deterministic polynomial-time rounding; neither manuscript identifies the unconditional degree-four sum-of-squares ratio.

Mathematical statement of the claimed result

Manuscript 1.
Let $\operatorname{MaxCut}(G)$ denote the largest weight crossing a vertex bipartition, and set \[ \alpha_{\rm GW}=\min_{-1\le\rho<1}\frac{2\arccos\rho}{\pi(1-\rho)}. \] For each fixed $\alpha\in(\alpha_{\rm GW},1]$, the claim is NP-hardness of returning a cut of weight at least $\alpha\operatorname{MaxCut}(G)$, even on simple unweighted graphs. Its more explicit weighted gap uses any rational $0<t<1$, $B(t)=2\arcsin(t)/\pi$, and $0<\varepsilon<(t-B(t))/4$: distinguishing the two promises \[ \operatorname{MaxCut}(G)\ge(1+t)/2-\varepsilon \quad\hbox{and}\quad \operatorname{MaxCut}(G)\le(1+B(t))/2+\varepsilon \] is NP-hard when the rational edge weights sum to one.
Manuscript 2.
For every fixed $\varepsilon,\delta\in(0,1/2)$, the claim gives $s\ge1$ and a deterministic polynomial-time $3$SAT reduction to explicit unweighted Unique Games over $K=\mathbb F_2^s$, on a simple bipartite graph with translation constraints $a(v_e)=a(u_e)+c_e$, satisfying \[ \varphi\text{ satisfiable}\Rightarrow\operatorname{val}(G_{\varphi})\ge1-\varepsilon, \qquad\varphi\text{ unsatisfiable}\Rightarrow\operatorname{val}(G_{\varphi})\le\delta. \] Alphabet size and polynomial constants depend only on the two fixed errors. For any fixed constraint-language instance $J$ with $A=\operatorname{OPT}(J)<B=\operatorname{SDP}_{R}(J)$, the associated consequence claims NP-hardness of distinguishing value at least $B-\eta$ from value at most $A+\eta$ for any fixed $0<\eta<(B-A)/2$.

Outline of the argument

For manuscript 1 (family 102; 2026-09-23), an affine game is composed directly with folded Gaussian sign tables. Excess stability reveals a hidden coordinate through restriction Fourier mass and vector-valued hashing, yielding endpoint labelers that contradict the outer game's low value.

For manuscript 2 (family 102; 2026-09-23), a latent quadratic alphabet and matrix-slice tests supply an outer permutation game. High acceptance decodes agreeing advice strategies, whereas clean-coordinate estimates from the unsatisfiable parity instance force their agreement to decay, giving the soundness contradiction.

Formal verification

For the selected results, the Lean scope page identifies OptimalMaxCut.lean and OAI.OptimalMaxCut.main, and UniqueGamesTheorem.lean and OAI.UniqueGamesTheorem.theorem11. The other Comparator links belong to companion papers in the same family. This scope concerns the stated hardness theorems; it does not cover the unconditional degree-four integrality ratio or the near-bipartite question. The site has not run these Lean files or independently checked their proofs.

Status caveat

The manuscripts were produced by an internal OpenAI model. OpenAI cautions that results without formalization can contain mistakes. This site has not independently checked the proofs; the label records the scope of OpenAI's claim.

Sources

Go to contribution →