Exponential semidefinite complexity of perfect matching 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

Exponential semidefinite complexity of perfect matching

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:	1
Category:	Theoretical computer science	Lean version:	YES! ✔
Rate this game! 4.0 out of 5 (8,642 votes)

>>> How to Play <<<

Exponential semidefinite complexity of perfect matching. Proves that every exact semidefinite lift of the perfect matching polytope has exponential size, answering Rothvoss's polynomial-size lift question negatively. The bound holds even for the positive semidefinite rank of its odd-cut slack matrix after any fixed shift $0\lt \rho\lt 1$, allowing arbitrary real positive semidefinite factors.

>>> Level Select <<<

LEVEL 1 Exponential PSD rank of positively shifted matching matrices

released 2026-10-05 | 3 theorems · 6 lemmas · 12 proofs · 9,888 words | PLAY LEVEL 1 » (pdf)

For every fixed $0\lt \rho\lt 1$, the matrix indexed by odd vertex sets U and perfect matchings M of K_n, with entries $|M\cap\delta(U)|-1+\rho$, has real positive semidefinite rank $2^{\Omega(n)}$ as even n tends to infinity. Here $\delta(U)$ is the edge cut of U. Consequently, every exact semidefinite lift of the perfect matching polytope has exponential size.

More Theoretical computer science Games!
A factor-two approximation for shortest common superstring	Exponential state costs for two-way automata	Fourier transforms below $n\log n$ HOT!	Polynomial mixing of graph switches with prescribed degrees
A counterexample to the quadratic sensitivity conjecture	The complexity of Weisfeiler–Leman refinement	Generalized star height at most three	Sharp homogeneous depth-five complexity of matrix products

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