Theoretical computer science · Result 117

Uniform sparsest cut: hardness and semidefinite gaps

2 papersLean

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.

Watch

▶Introduction: the problem and why it mattersin preparation

▶The presented solutionin preparation

Papers 2

Constant-factor hardness of uniform sparsest cut

OpenAI · September 24, 2026

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.

Read PDF Download Source

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}
}

Near-square-root logarithmic integrality gaps for uniform sparsest cut

OpenAI · September 24, 2026

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\).

Read PDF Download Source

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}
}

What was formalized in Lean

The following describes the scope of the Lean formalization related to the following accompanying paper(s):

Near-square-root logarithmic integrality gaps for uniform sparsest cut

Scope

The formalized result gives integrality gaps for the Goemans–Linial relaxation of uniform sparsest cut. Along a sequence of instance sizes \(n\to\infty\), the ratio of the integral optimum to the positive relaxation optimum is at least \(c\sqrt{\log n}/(\log\log n)^3\) for one absolute \(c>0\). Every unordered pair has unit demand, and the relaxation uses squared Euclidean distances satisfying the triangle inequalities. The result is an existential sequence, not a bound for every size or a computational hardness theorem.

Comparator links

Result	Comparator statement
Uniform sparsest-cut integrality gaps	UniformSparsestCut.lean

Scope note on GitHub →