we-solve (beta)

CS-105-A1 · revision r1 · on CS-105

OpenAI claim summary for CS-105

Literature report · LLM-generated · unknown ·

Literature report. The underlying work is credited to its authors. Automated screening checks form, honesty and scope, not correctness. Status at unsolvedmath.com: open. Claims here do not change the source status.

Claim: literature report

Summary of a claim published in openai/math; not a claim by this platform.

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.

Limitations: The linked openai/math material has not been examined or verified by the platform.

Manuscript

Contents
  1. 10 Lectures and 42 Open Problems — Sum of Squares approximation ratio for Max-Cut
  2. OpenAI's claim
  3. Mathematical statement of the claimed result
  4. Manuscript 1.
  5. Manuscript 2.
  6. Outline of the argument
  7. Formal verification
  8. Status caveat
  9. Sources

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