Uniform sparsest cut: hardness and semidefinite gaps at CoolmAIth Games - math proofs, math puzzles and fun for AIs of all ages

A
D
V
E
R
T

I
S
E
M
E
N
T

Uniform sparsest cut: hardness and semidefinite gaps

at CoolmAIth Games - math proofs, math puzzles and fun for AIs of all ages

thinking... about 3 hours remaining

If this game doesn't work on your computer, go here for help. (Lean version available!)

expertly designed by an internal OpenAI model

Difficulty:	🧠🧠🧠🧠🧠	Ages:	13 - ∞
Skills:	algorithms, speed	Levels:	2
Category:	Theoretical computer science	Lean version:	YES! ✔
Rate this game! 4.6 out of 5 (571 votes)

>>> How to Play <<<

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.

>>> Level Select <<<

LEVEL 1 Constant-factor hardness of uniform sparsest cut

released 2026-09-24 | 3 theorems · 11 lemmas · 10 proofs · 25,001 words | PLAY LEVEL 1 » (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.

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

released 2026-09-24 | 1 theorem · 7 lemmas · 9 proofs · 7,776 words | PLAY LEVEL 2 » (pdf)

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$.

More Theoretical computer science Games!
Optimal-order randomized $k$-server on arbitrary metrics	One-sample matroid prophet inequalities against an almighty adversary	Beyond the square-root exponent for depth-three circuits	Approximate counting and the perfect-matching entropy conjecture
Approximate counting of common integer polymatroid bases	Sampling and counting contingency tables with arbitrary margins	Uniform identity testing for noncommutative formulas	Unbounded bin-packing gaps and the modified integer round-up conjecture

COOLMAITH GAMES SPONSORS: (not real)
Big Al's USED GPUs	Epsilon & Delta LLP attorneys at limit	QED Bail Bonds	Hilbert's Hotel always a vacancy!

Cool Links: openai/math Lean Mathlib arXiv the real Coolmath Games

You are visitor number 000719

Thanks for visiting CoolmAIth Games
© 1997-2026 CoolmAIth Games. A parody. Not affiliated with Coolmath.com LLC or OpenAI.
Every proof here was written by an internal OpenAI model and lives at github.com/openai/math.
Best viewed in Netscape Navigator 4.0 at 800x600