VibeMathedMath problems solved with AI
Sign in

NP-hardness of approximating Uniform Sparsest Cut within every constant factor

Uniform Sparsest Cut asks, for a graph on NN vertices with nonnegative capacities cijc_{ij}, for the minimum over nonempty proper SS of ∑i∈S,j∉Scij/(∣S∣(N−∣S∣))\sum_{i\in S,j\notin S}c_{ij}/(|S|(N-|S|)). Arora, Rao and Vazirani gave an O(log⁡N)O(\sqrt{\log N}) approximation. Exact computation is NP-hard, but approximation lower bounds were known only under assumptions: Ambuhl, Mastrolilli and Svensson ruled out a PTAS assuming SAT has no subexponential randomized algorithms, and the Small-Set Expansion hypothesis gives hardness of every constant factor. For the nonuniform problem, hardness of every constant factor follows from the Unique Games Conjecture. Is it NP-hard, with no unproved hypothesis, to approximate Uniform Sparsest Cut within some constant factor, or within every constant factor?

Result
Proved(see note)
Status
Candidate (review pending)
AI contribution
AI-discovered
Method
Argument
Field
Hardness of approximation; graph partitioning
Posed by
Open problem in the hardness-of-approximation literature; discussed by Ambuhl, Mastrolilli and Svensson and by Manurangsi and Trevisan
Year posed
—
Years open
—
Solved
2026-09-24
Model
Unreleased internal OpenAI model
Vendor
OpenAI
Collaborators
—
Verification
Unreviewed
Publication
Announced
Collection
OpenAI math release (October 2026), version adc7f12
Significance
45 / 100
Disclosed cost
—
Wikipedia
No dedicated article

What was actually shown

Theorem 1.1: for every fixed C>1C>1 there is a polynomial-time reduction from 3SAT producing uniform-demand instances with a multiplicative gap CC, so approximating Uniform Sparsest Cut within any constant factor is NP-hard. The constants and exponents of the reduction depend on CC. It does not give a superconstant (for instance log⁡N\sqrt{\log N}-type) hardness factor, does not address Balanced Separator directly, and says nothing about the Small-Set Expansion hypothesis itself.

What the AI did

The release README says the results were produced by an unreleased internal OpenAI model with a fixed procedure, on average about three hours of ChatGPT Pro thinking compute per result, and that some outputs build on earlier model results. This result is not among the README's exceptions (the Hodge conjecture for CM abelian varieties and the Re(s) > 11/12 zero-free region). The manuscript is authored 'OpenAI' and names no human author. The family has two manuscripts dated September 24, 2026: the hardness reduction (this entry) and a separate integrality-gap construction (its own entry).

Verification

No independent mathematician has checked this yet. Checked here: Theorem 1.1 was read against the question. For every fixed C>1C>1 it gives a polynomial-time reduction from 3CNF satisfiability to graphs with nonnegative rational capacities and unit demand on every pair, with Φ(G)≤a\Phi(G)\le a for satisfiable and Φ(G)>Ca\Phi(G)>Ca for unsatisfiable formulas, using no unproved complexity hypothesis. That answers the question as posed (every constant factor, exact uniform demands, deterministic Karp reduction). The PCP-style proof (Garcia-Stichtenoth tower tests, rare-event extraction, cut-variance analysis) was not refereed and is not formalised; the Lean formalization in this family covers only the integrality-gap companion.

Sources

Changelog1 change

Discussion