Browse › Theoretical computer science › 117 Uniform sparsest cut: hardness and semidefinite gaps
Near-square-root logarithmic integrality gaps for uniform sparsest cut
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 construct uniform sparsest-cut instances whose Goemans–Linial semidefinite integrality gap is at least $c\sqrt{\log n}/(\log\log n)^3$ along a sequence $n\to\infty$. The demand is one between every pair of distinct vertices, and the capacities are nonnegative real numbers. This matches the Arora–Rao–Vazirani upper bound up to a power of $\log\log n$.
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). Describes the formalized statement as an existential sequence of uniform-demand Goemans–Linial instances with positive relaxation optimum and integrality gap at least $c\sqrt{\log n}/(\log\log n)^3$, and links the comparator statement. [family-level]
- OpenAI, UniformSparsestCut.lean (comparator statement
mainGap) (openai/math, commit adc7f12). Lean statement of Theorem 1.1, the ratio $\mathrm{OPT}/\mathrm{glValue}$ along a sequence $n_j\to\infty$; the proof is asorryplaceholder, which is how comparator challenge files are written. - OpenAI, OAI/Combinatorics/SparsestCut/Main.lean (
OAI.UniformSparsestCut.mainGap) (openai/math, commit adc7f12). The release's Lean proof of the main gap theorem, assembled from lemmas in other modules of the same directory.
Possibly relevant literature (found by the agent, not checked)
- Georgios Stamoulis, Integrality Gap Bounds for the Goemans-Linial SDP on Finite Abelian Cayley Graphs (arXiv:2609.05368, 2026-09-04). Studies the same Goemans–Linial relaxation of uniform sparsest cut on abelian Cayley graphs, showing exactness in some cases and a family with gap exactly 16/15; it bears on the paper's discussion of uniform-demand gap lower bounds.
Elsewhere
- VibeMathed: Problem record
- Emergent Mind: family 117
Independent sites; their content is not reviewed here.
Cite
@misc{OAI:Near-square-root-logarithmic-integrality-gaps-for-uniform-sparsest-cut-September-24-2026,
author = {{OpenAI}},
title = {{Near-square-root logarithmic integrality gaps for uniform sparsest cut}},
howpublished = {OpenAI Math Release preprint
\href{https://github.com/openai/math/blob/main/preprints/Near-square-root-logarithmic-integrality-gaps-for-uniform-sparsest-cut-September-24-2026/Near-square-root-logarithmic-integrality-gaps-for-uniform-sparsest-cut-September-24-2026.pdf}{OAI:Near-square-root-logarithmic-integrality-gaps-for-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:
- Constant-factor hardness of uniform sparsest cut · September 24, 2026