A cubic permanent–determinant lower bound 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

A cubic permanent–determinant lower bound

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.5 out of 5 (6,071 votes)

>>> How to Play <<<

A cubic permanent–determinant lower bound. Proves an $\Omega(n^3)$ lower bound for the border determinantal complexity of the $n\times n$ permanent over ℂ. Even coefficientwise limits of determinants of affine-linear matrices require matrix size at least $cn^3$, for an absolute c > 0 and all sufficiently large n; the same bound therefore holds for exact representations.

>>> Level Select <<<

LEVEL 1 A cubic lower bound for border determinantal complexity of the permanent

released 2026-09-24 | 2 theorems · 10 lemmas · 25 proofs · 15,208 words | PLAY LEVEL 1 » (pdf)

We prove that the complex border determinantal complexity of the $m\times m$ permanent is $\Omega(m^3)$, allowing arbitrary affine-linear determinant representations and coefficientwise limits. It also gives cubic lower bounds for exact determinantal complexity and for the numbers of vertices and edges in affine-linear algebraic branching programs, including coefficientwise limits with a fixed vertex or edge budget.

More Theoretical computer science Games!
Generalized star height at most three	Sharp homogeneous depth-five complexity of matrix products	The quasilinear PCP-for-PPAD conjecture	One-tape time simulation in two-fifths-power space
Subset Sum in $O(2^{0.49n})$ time HOT!	Subpolynomial queries for log-concave sampling	Memory–sample lower bounds for noiseless Gaussian regression	The existential theory of the reals and existential–universal sentences in the counting hierarchy

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