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. (Lean)

Manuscripts (2)

Constant-factor hardness of uniform sparsest cut

September 24, 2026 · source · cite as \cite{OAI:Constant-factor-hardness-of-uniform-sparsest-cut-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.

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

September 24, 2026 · source · Lean formalization available · cite as \cite{OAI:Near-square-root-logarithmic-integrality-gaps-for-uniform-sparsest-cut-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.

Result 117 · Theoretical computer science. Imported from openai/math, a collection of manuscripts produced by an OpenAI model; results are at different stages of verification. Discussion below is by Lemma members.