oai-math-revised beta

Browse › Theoretical computer science › 117 Uniform sparsest cut: hardness and semidefinite gaps

Constant-factor hardness of uniform sparsest cut

OpenAI · September 24, 2026

Lean

Open PDFCite Report a problem Add a reference or comment Interested in working on this Start a discussion

Edit NOTES.md · Existing issues · Source on GitHub

Abstract

We prove that, for every fixed C > 1, approximating Uniform Sparsest Cut within factor C is NP-hard. The output graphs have nonnegative rational capacities and unit demand between every pair of distinct vertices.

If the PDF does not display here, open it directly: Open PDF.

Notes

No notes yet. Add a reference, a comment or your name with the buttons above, or edit NOTES.md on GitHub.

Automatically collected notes (unreviewed)

work in progress

Collected automatically by AI tools (Claude Opus 5.5 and GPT-6 Astra, 2026-10-21) and not checked by a person. May be wrong or incomplete. Report an error.

Formalization

  • OpenAI math release, Lean scope notes for family 117 (release Lean docs, 2026-10-06). The family's Lean scope note covers only the companion integrality-gap paper and says the formalized result is "not a bound for every size or a computational hardness theorem"; the NP-hardness reduction of this paper is not covered. [family-level]

Elsewhere

Independent sites; their content is not reviewed here.

Cite

@misc{OAI:Constant-factor-hardness-of-uniform-sparsest-cut-September-24-2026,
  author = {{OpenAI}},
  title = {{Constant-factor hardness of uniform sparsest cut}},
  howpublished = {OpenAI Math Release preprint
                  \href{https://github.com/openai/math/blob/main/preprints/Constant-factor-hardness-of-uniform-sparsest-cut-September-24-2026/Constant-factor-hardness-of-uniform-sparsest-cut-September-24-2026.pdf}{OAI:Constant-factor-hardness-of-uniform-sparsest-cut-September-24-2026}},
  year = {2026}
}

Lean formalization

OpenAI provides Lean files for this family: lean/docs/117.md. The Lean statements have not been checked by people against the paper's claims.

Family 117: Uniform sparsest cut: hardness and semidefinite gaps

Proves that approximating Uniform Sparsest Cut within any fixed constant factor is NP-hard, even with nonnegative rational capacities and unit demands. The Goemans–Linial semidefinite relaxation also has integrality gaps of order at least $\sqrt{\log n}/(\log\log n)^3$, approaching the square-root-logarithmic upper bound.

Other papers in this family: