Hard to approximate?
A claimed unconditional proof that uniform sparsest cut has no constant-factor approximation unless P = NP, and near-square-root-logarithmic gaps for its semidefinite relaxation
Covers result 117 in OpenAI’s catalog: all 2 papers. See its connections to other results and the work it cites.
6:21. English captions available. The video loads from YouTube when you press play.
Chapters
The claims, in plain words
Uniform sparsest cut asks for the weakest way to split a network: among all ways to divide the vertices into two sides, minimize the capacity crossing the cut divided by the number of vertex pairs it separates. Because the denominator counts every separated pair, small sides matter too: a barbell (two cliques joined by one edge) is cut at its bridge, while a vertex hanging by a weak edge can be cut off alone.
Leighton and Rao approximated it within a logarithmic factor using multicommodity flows; Arora, Rao and Vazirani improved this to O(√log n) using the Goemans–Linial semidefinite relaxation, which gives each vertex a vector and requires the squared distances to obey the triangle inequality. Finding the exact optimum is NP-hard, but hardness of approximation was only conditional: Ambühl, Mastrolilli and Svensson ruled out an approximation scheme unless SAT has randomized subexponential-time algorithms, and every constant factor was ruled out under the Small-Set Expansion hypothesis. For uniform demands, the relaxation’s known integrality gaps grew like log log n (Devanur, Khot, Saket and Vishnoi) and then eΩ(√log log n) (Kane and Meka).
Result 117 is two OpenAI preprints dated September 24, 2026. The first (48 pages) claims that for every fixed C > 1, approximating uniform sparsest cut within factor C is NP-hard, with no unproven hypothesis: a polynomial-time reduction from 3-SAT produces a graph with nonnegative rational capacities, unit demand on every pair, and a threshold a, such that satisfiable formulas give a sparsest-cut value at most a and unsatisfiable ones a value above C·a. The second (22 pages) constructs instances whose Goemans–Linial integrality gap is at least c√(log n)/(log log n)³ along a sequence of sizes, within (log log n)³ of the Arora–Rao–Vazirani upper bound.
What it doesn’t claim
The hardness result concerns fixed constant factors; it does not rule out the O(√log n) approximation or anything between constants and √log n. The gap holds along a sequence of sizes and is asymptotic: ignoring constants, the shape √(log n)/(log log n)³ only overtakes log log n for numbers of vertices with tens of billions of digits.
Where it stands
- Posted as preprints
- OpenAI, 48 and 22 pages, dated September 24, 2026
- Peer reviewed
- Not yet
- Checked in Lean
- OpenAI published a Lean proof of the integrality-gap theorem, not of the hardness reduction (a few uncatalogued files cover pieces of it); we have not run the check
Last checked October 19, 2026. The preprints have not been revised. OpenAI published a Lean formalization of the integrality-gap theorem, as an existential sequence of instances, in 55 files and 9,934 lines (not counting Mathlib), matched against its comparator statement. The hardness reduction, the longer claim, is not formalized. Seven uncatalogued files in the same folder (not linked from the collection’s catalog), 928 lines excluding Mathlib, with no unproved steps by our search, formalize pieces of its Section 7: the encodings, the final completeness and soundness inequalities, and weight estimates. They take the reduction’s yes and no cases as assumptions, and no theorem states NP-hardness. We have not run the check. Neither paper is among those OSVerify reviewed, and we have seen no expert review.
How the proofs go
- Tests and valuations. The hardness proof starts from an algebraic test system for 3-SAT. A short list of directions from the Garcia–Stichtenoth tower of function fields ensures that a quadratic form nonzero somewhere on the list rarely vanishes on it. Each test reads a few proof bits, and no position is queried more than a fixed multiple of the uniform rate. An approximately calibrated, order-preserving valuation of the test predicates decodes a satisfying assignment.
- From a cut to an assignment. A sparse cut may separate only a tiny amount of demand, so every error is measured relative to that amount. A cut of small cost forces a rare successful event: a Boolean response to a conjunction of many independently sampled predicates. Conditioning on it and forcing the resulting density near two values extracts one valuation. Rounding scores to grids and replicating vertices gives a polynomial-size graph with exactly unit demand on every pair.
- The semidefinite gap. The construction needs a negative-type metric with large average distance such that every non-expanding map into L1 keeps only a small fraction of it, in the average-distortion view of Linial, London and Rabinovich, and Rabinovich. Points of a parameter cube are labelled through many rounded linear charts; Hilbert-space features have squared distances approximating a multiple of distance in the cube; a scale integral of Gaussian kernels repairs the triangle inequalities; and a Maurey–Pisier first-moment inequality bounds what any such map can keep. Earlier general-demand gaps on the Heisenberg group could not do this: those spaces embed into a line with constant average distortion.
The numbers in the video
- Brute force over all cuts: the barbell’s optimum is 1/25, at the bridge; a 7-clique with one vertex attached by capacity 0.2 has optimum 1/35, cutting off that vertex.
- The Goemans–Linial relaxation, solved as a semidefinite program with all triangle inequalities, equals the true optimum on five small graphs: no gap shows up at that size.
- Without the triangle inequalities, the spectral bound’s ratio to the optimum on cycles grows from 1.33 at 6 vertices to 2.89 at 14.
- Ignoring constants, √(log n)/(log log n)³ stays above log log n only once log log n exceeds about 26: vertex counts with about 93 billion digits.
Read the source
- Constant-factor hardness of uniform sparsest cut (PDF), 48 pages.
- Near-square-root logarithmic integrality gaps for uniform sparsest cut (PDF), 22 pages.
- The Lean scope note.
- The collection’s catalog, where this is result 117.
The 2 papers in this result
OpenAI groups related papers, such as alternative proofs, supporting results and consequences, into one result; we label the first paper it lists the main paper and the others companions.
Transcript
Read the full script
0:00The weakest cut
Uniform sparsest cut asks for the weakest way to split a network. Among all ways to divide the vertices into two sides, it minimizes the capacity crossing the cut divided by the number of vertex pairs the cut separates. Because that denominator counts every separated pair, small sides matter too. A barbell, two cliques joined by one edge, is cut at its bridge, while a vertex hanging by a weak edge can be cut off alone. Sparse cuts drive divide-and-conquer algorithms and clustering, and they measure how well a network is connected. In our check, brute force over all cuts found the barbell’s optimum at 1/25, and the weakly attached vertex alone at 1/35. Leighton and Rao used multicommodity flows to approximate it within a logarithmic factor. Arora, Rao and Vazirani improved this to the square root of log n, using the Goemans–Linial semidefinite relaxation: give each vertex a vector, and require the squared distances to obey the triangle inequality. On hardness, finding the exact optimum is NP-hard, but for approximation only conditional results were known: Ambühl, Mastrolilli and Svensson ruled out an approximation scheme unless SAT has randomized subexponential-time algorithms, and every constant factor was ruled out under the Small-Set Expansion hypothesis. For the relaxation with uniform demands, the known gaps grew only like log log n, by Devanur, Khot, Saket and Vishnoi, and then like e^(c√(log log n)), by Kane and Meka.
1:40The claims
Result 117 is two OpenAI preprints dated September 24. The first, 48 pages, claims that for every fixed constant C greater than one, approximating uniform sparsest cut within a factor C is NP-hard, with no unproven hypothesis. It gives a polynomial-time reduction from 3-SAT to graphs with nonnegative rational capacities and unit demand between every pair of vertices, together with a threshold a. A satisfiable formula gives a sparsest-cut value at most a, and an unsatisfiable one gives a value above C·a. The second, 22 pages, constructs instances whose Goemans–Linial integrality gap is at least a constant times √(log n)/(log log n)³, along a sequence of sizes tending to infinity. This nearly matches the square-root-of-log-n upper bound of Arora, Rao and Vazirani. OpenAI published a Lean formalization of the gap theorem, 55 files and about 10,000 lines; the hardness reduction is not formalized. We have not run the Lean check ourselves.
2:54How the proofs go
The hardness proof begins with an algebraic test system for 3-SAT. A short list of directions, taken from the Garcia–Stichtenoth tower of function fields, ensures that a quadratic form that is nonzero somewhere on the list rarely vanishes on it. The tests read a few proof bits, and no position is queried more than a fixed multiple of the uniform rate. A valuation that is approximately calibrated and order-preserving on the test predicates would then decode a satisfying assignment. The central difficulty is that a sparse cut may separate only a tiny amount of demand, so every error must be measured relative to that amount. The proof turns a cut of small cost into a rare successful event: a Boolean response to a conjunction of many independently sampled predicates. Conditioning on that event, and forcing the resulting density near two values, extracts a single valuation, and hence a satisfying assignment. Finally, scores are rounded to grids and vertices are replicated, giving a graph of polynomial size with exactly unit demand on every pair. The gap construction needs a negative-type metric with large average distance, such that every non-expanding map into L1 keeps only a small fraction of it, in the average-distortion view developed by Linial, London and Rabinovich, and by Rabinovich. It labels the points of a parameter cube through many rounded linear charts, builds Hilbert-space features whose squared distances approximate a multiple of distance in the cube, and repairs the triangle inequalities with a scale integral of Gaussian kernels. A first-moment inequality, proved by the Maurey–Pisier Gaussian rotation method, bounds what any such map into L1 can keep. Earlier general-demand gaps on the Heisenberg group could not do this: as Cheeger, Kleiner and Naor note, those spaces embed into a line with constant average distortion. In our check, the Goemans–Linial relaxation, solved as a semidefinite program, matched the true sparsest cut on five small graphs, so no gap shows up at this size. Dropping the triangle inequalities leaves the spectral bound, whose ratio on cycles grew from 1.33 at 6 vertices to 2.89 at 14. And ignoring constants, the new bound’s shape stays above log log n only once log log n exceeds about 26, for vertex counts with about 93 billion digits. The claim is asymptotic.
5:33Where it stands
The preprints are not peer reviewed and have not been revised. The Lean formalization covers the integrality-gap theorem, as an existential sequence of instances; the hardness reduction, the longer claim, is not formalized. We have not run the check. Neither paper is among those OSVerify reviewed, and we have seen no expert review. If they hold, uniform sparsest cut has no constant-factor approximation unless P equals NP, without the Small-Set Expansion hypothesis that earlier hardness needed, and the integrality gap of its basic semidefinite relaxation comes within the cube of log log n of its known upper bound, at least along a sequence of sizes.
Spot a mistake?
This episode simplifies on purpose, but it shouldn’t be wrong. If something is, open an issue on GitHub or leave a comment on YouTube. Corrections are noted here with a date.