Constant-factor hardness of uniform sparsest cut
Status OpenLLM status Open unverified
Top Open Problems unknownunknown Not reported cataloguedOpenOpenStatement
Definitions and mathematical statement
Statement recorded in the supplied source.
For each fixed $C>1$, is approximating uniform sparsest cut within factor C NP-hard on explicitly encoded finite undirected graphs with nonnegative rational capacities and unit demand between each pair of distinct vertices?Short English statement
For each fixed $C>1$, is approximating uniform sparsest cut within factor C NP-hard on explicitly encoded finite undirected graphs with nonnegative rational capacities and unit demand between each pair of distinct vertices?Sources
- S1 Original question source or mathematical context. https://afonsobandeira.wordpress.com/2015/10/05/10l42pcheeger/.
- S2 OpenAI, manuscript citation page. Source of the formulation motivating this local problem. https://github.com/openai/math/blob/adc7f1241b42e322a6451854ab7e4b4c146bf78a/preprints/Constant-factor-hardness-of-uniform-sparsest-cut-September-24-2026/README.md.
Statement licence: CC-BY-4.0 · Source file
Contributions 1
OpenAI claim summary for CS-169
The result supplies the conclusion in this problem with its displayed hypotheses and quantifiers. The broader statements and applications in the manuscript are kept separate from the particular question above. The supporting result is manuscript 1 (family 117; 2026-09-24).
Constant-factor hardness of uniform sparsest cut
OpenAI's claim
OpenAI presents the following claims relevant to this question, with manuscript numbers following paper order in Sources. In manuscript 1 (family 117; 2026-09-24), the asserted result is that Uniform Sparsest Cut is NP-hard to approximate by any fixed factor greater than one, for rational capacities and unit pair demands.Mathematical statement of the claimed result
Manuscript 1.
For an undirected graph whose capacities are nonnegative rational numbers, with each pair of distinct vertices assigned demand one, set \[ \Phi(G)=\min_{\varnothing\ne S\subsetneq V} \frac{\sum_{u\in S,v\notin S}c_{uv}}{|S|\,|V\setminus S|}. \] For each fixed $C>1$, the claimed polynomial-time reduction from $3$CNF satisfiability outputs $G$ and positive rational $a$ with \[ \varphi\text{ satisfiable}\Rightarrow\Phi(G)\le a, \qquad\varphi\text{ unsatisfiable}\Rightarrow\Phi(G)>Ca. \] All output bit lengths are polynomial in formula size for fixed $C$; the demands remain exactly one.Outline of the argument
For manuscript 1 (family 117; 2026-09-24), an additive tower produces a short explicit direction list with robust quadratic support. A mixing parity test and deterministic correction enforce almost-quadratic consistency; the resulting gap is converted to a graph while preserving uniform demands.Formal verification
No Lean formalization is listed at this snapshot for manuscript 1 (family 117; 2026-09-24).This site has not executed the Lean code. Described statement coverage is not an independent proof check.
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
- OpenAI, Constant-factor hardness of uniform sparsest cut, 2026-09-24; citation key
OAI:Constant-factor-hardness-of-uniform-sparsest-cut-September-24-2026. PDF (GitHub); PDF (direct); Manuscript page and citation; Latest version; Statement source: thm:main. - Family 117: Lean scope.
- OpenAI catalogue entry.