Approximability of uniform sparsest cut
From OpenAI Aftermath
Uniform sparsest cut asks, for a finite graph with nonnegative edge capacities, for a nonempty proper vertex set S that minimizes the capacity crossing the cut divided by |S|(N − |S|), the number of vertex pairs the cut separates; it is the sparsest-cut problem with unit demand between every pair of distinct vertices. The semidefinite programming algorithm of Arora, Rao and Vazirani approximates it within a factor O(√log n), and earlier hardness of approximation within every constant factor was known only under complexity hypotheses. Two manuscripts in OpenAI's public mathematics collection (github.com/openai/math), listed together as its result 117 and both dated 24 September 2026, claim that approximating uniform sparsest cut within any fixed constant factor is NP-hard, and that the Goemans–Linial semidefinite relaxation has integrality gap at least c√(log n)/(log log n)3 along a sequence of instance sizes. The collection includes a Lean formalization of the integrality-gap theorem; the hardness reduction is not formalized.
Background
- As recounted in the introductions of the manuscripts:
- Leighton and Rao developed the flow–cut approach and its logarithmic approximation guarantees, and Arora, Rao and Vazirani improved the factor to O(√log n) through their semidefinite relaxation and geometric separation theorem.
- Matula and Shahrokhi proved NP-hardness of finding sparsest cuts, and Bonsma, Broersma, Patel and Pyatkin proved NP-completeness for unweighted graphs with the uniform denominator. Ambühl, Mastrolilli and Svensson showed that a polynomial-time approximation scheme would give probabilistic SAT algorithms of time 2nε for every fixed ε > 0. Raghavendra, Steurer and Tulsiani obtained every-constant-factor gaps for balanced separator from the Small-Set Expansion hypothesis, which yield the same for uniform sparsest cut under that hypothesis. For nonuniform demands, Chawla, Krauthgamer, Kumar, Rabani and Sivakumar proved every-constant-factor hardness under the Unique Games Conjecture, and Gupta, Talwar and Witmer proved NP-hardness with a 17/16 − ε threshold for treewidth-two supply graphs.
- For uniform demands, Devanur, Khot, Saket and Vishnoi obtained an Ω(log log n) integrality gap for the Goemans–Linial relaxation, and Kane and Meka obtained eΩ(√log log n). For general demands, Khot and Vishnoi disproved the Goemans–Linial conjecture, Naor and Young proved the lower bound Ω(√log n), and Chang, Naor and Ren proved the matching upper bound; Cheeger, Kleiner and Naor explain that their bounded-doubling examples have constant average distortion into a line and cannot give a diverging uniform gap.
The original results
- Claim, hardness. Theorem 1.1 of Constant-factor hardness of uniform sparsest cut states that for every fixed real constant C > 1 there is a polynomial-time reduction from 3CNF satisfiability to finite undirected graphs with nonnegative rational capacities and exactly unit demands, together with a positive rational threshold a, such that satisfiable formulas give a sparsest-cut value at most a and unsatisfiable ones a value above Ca. The manuscript states that the reduction uses no unproved complexity hypothesis.
- Method, as described: an algebraic test system for 3CNF built from evaluation vectors on the Garcia–Stichtenoth tower, bit tests with uniformly bounded query probabilities, the extraction of a Boolean valuation from a rare successful event by an entropy argument, scores and smoothed comparison paths whose errors are proportional to the cut variance, and a final rounding and replication step that produces exactly the uniform denominator. The manuscript also notes that every-constant-factor hardness for the nonuniform problem follows from the conditional reduction of Chawla et al. combined with the collection's Unique Games Theorem, and that its direct reduction is independent of that consequence.
- Claim, integrality gaps. Theorem 1.1 of Near-square-root logarithmic integrality gaps for uniform sparsest cut states that there are an absolute constant c > 0 and uniform-demand instances on nj → ∞ vertices, with nonnegative real capacities and positive relaxation value, whose ratio of the integral optimum to the Goemans–Linial optimum is at least c√(log nj)/(log log nj)3. The manuscript states that this matches the Arora–Rao–Vazirani upper bound up to a power of log log n.
- Method, as described: a negative-type semimetric built from many rounded linear charts of a common parameter cube, with Hilbert vectors from a common smooth feature map, such that every contraction into ℓ1 preserves only a small fraction of the average distance; cut-cone duality in the average-distortion framework of Linial, London and Rabinovich and of Rabinovich then gives the capacities.
- Formalization, as described by the repository. The scope note links only the integrality-gap manuscript and states that the formalized result gives integrality gaps for the Goemans–Linial relaxation along a sequence of instance sizes, as an existential sequence, "not a bound for every size or a computational hardness theorem". The Comparator statement is
UniformSparsestCut.lean. - Sources (openai/math repository, commit
7ef5c0c): Constant-factor hardness of uniform sparsest cut and Near-square-root logarithmic integrality gaps for uniform sparsest cut, both dated 24 September 2026.
Public follow-up work
| Date | Work | Relation | Public claim | Public status (checked 30 October 2026) |
|---|---|---|---|---|
| 2026-10-07 | Uniform sparsest cut: hardness and semidefinite gaps, an article of the Latent Seminar blog at lowrank.github.io | Reading (exposition) | Explains the two claims: every-constant-factor NP-hardness of uniform sparsest cut with rational capacities and unit demand on every pair, and a Goemans–Linial integrality gap within a power of log log n of the square root of log n. It explains why small cuts force errors relative to the separated demand, how sampled masses become actual vertex counts, and the average-distortion obstruction behind the semidefinite gap. | Blog article; it states that its review covers statements, introductions and selected proof mechanisms and is not an independent verification of the complete proofs. |
| 2026-10-08 | MathVet (GitHub; review of openai/math, tables at repository commit c76f1e4, 14 October 2026) |
Review (fidelity of the formal statements) | Rates this family "partial" and records a sandboxed Comparator pass for UniformSparsestCut. Its note states that only the Goemans–Linial integrality gap is formalized, with real capacities and along a sequence of sizes, and that the NP-hardness of constant-factor approximation, the first claim of the summary, is not stated. It lists the negative-type and optimum definitions as checked. |
MathVet states that it does not claim any theorem false and reports what was machine-checked as stated. |
| 2026-10-10 | cert-machine, openai/math lane K, run 38019899278 | Verification (two kernels) | Records that Lean's default kernel and the nanoda kernel accept the UniformSparsestCut solution, in 470 s. C. Toledo's report lists the challenge among those certified by both kernels. |
Repository. The run concerns the formalized integrality-gap statement only. |
| 2026-10-16 | J. Jardine, Lattice24, referee review rank_195 in JJardine919/openai-math-audit (archived at Zenodo 10.5281/zenodo.23422995) | Review (AI-assisted audit) | Reports no gap in the hardness manuscript. It states that it checked line by line the finite-graph construction of Section 7, the decoding of Section 3, the bit-test system of Section 2, the rare-event lemma of Section 4 and the score and path estimates of Sections 5 and 6. As a coverage caveat it states that it did not re-derive the construction of the quadratic evaluation pencil from the Garcia–Stichtenoth tower in Section 1 or every union-bound constant of the cell-marking rules. | Part of an audit of the collection's manuscripts that the audit describes as complete. The reviews are published under CC BY 4.0. No review of the integrality-gap manuscript appears in the audit. |
| 2026-10-16 | AI Proved What?, episode 117 Hard to approximate?, remade version of 26 October 2026 | Reading (exposition) | Video explainer of the two claims: for every fixed C > 1, approximating uniform sparsest cut within factor C is NP-hard with no unproven hypothesis, by a polynomial-time reduction from 3-SAT to graphs with nonnegative rational capacities and unit demand on every pair; and instances whose Goemans–Linial integrality gap is at least a constant times the square root of log n divided by the cube of log log n along a sequence of sizes, within that cube of the Arora–Rao–Vazirani upper bound. The episode states that the hardness result concerns fixed constant factors and does not rule out the Arora–Rao–Vazirani approximation or anything between constants and the square root of log n, and that the gap is asymptotic, overtaking log log n only for vertex counts with tens of billions of digits. | Web page and video; the site states that its scripts and animations are produced with AI assistance and that the narration is an AI-generated voice. Status record last checked 27 October 2026: posted as preprints: OpenAI, 48 and 22 pages, dated September 24, 2026; under expert review: not yet; peer reviewed: not yet; checked in Lean: the integrality-gap theorem, not the hardness reduction; the site has not run the check. The page states that neither preprint has been revised and that the formalization of the integrality-gap theorem, an existential sequence of instances, has 55 files and 9,934 lines. It states that seven uncatalogued files in the same folder, 928 lines with no unproved steps by the site's search, formalize pieces of Section 7 of the hardness manuscript, taking the reduction's yes and no cases as assumptions, and that no theorem states NP-hardness. It states that neither paper is among those OSVerify reviewed and that it has seen no expert review. |
| 2026-10-18 (version 2; version 1: 14 July 2026) | M. Szyfelbein, D. Dereniowski, Graph Partitioning with Demands: Generalized Conductance and its Applications, arXiv:2607.13218v2 | Use (conditional) | Version 2 cites the OpenAI manuscript claiming constant-factor hardness of uniform-demand sparsest cut and derives, conditionally on that claim, constant-factor hardness for generalized conductance with uniform demands. Its hardness section states that the sparsest-cut hardness result has not been verified in Lean, so the corresponding conclusions are stated as conditional; it likewise does not treat the collection's Unique Games Theorem as an established proof. | arXiv preprint, version 2 of 18 October 2026. |
Notes
- The background summarizes the manuscripts' own account of earlier work.
- The list covers follow-ups found in public sources up to the date above; it is not a priority or completeness claim.
- See also The Unique Games Conjecture.
