Uniform sparsest cut: hardness and semidefinite gaps

What OpenAI claims

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 √(log n)/(log log n)³, approaching the square-root-logarithmic upper bound. (Lean)

Papers (2)

1. Constant-factor hardness of uniform sparsest cut

   24 September 2026 · Preprint, not peer reviewed · PDF

   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.

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

   24 September 2026 · Preprint, not peer reviewed · PDF

   We construct uniform sparsest-cut instances whose Goemans–Linial semidefinite integrality gap is at least c√(log n)/(log log n)³ along a sequence n → ∞. 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.

Status

Preprint. The papers have not been independently reviewed. Treat the result as OpenAI's claim until other mathematicians have checked it. If a video exists, it illustrates the statement; it is not the proof.