The asymptotic Gotsman–Linial conjecture 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

The asymptotic Gotsman–Linial conjecture

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.3 out of 5 (1,403 votes)

>>> How to Play <<<

Average sensitivity of polynomial threshold functions. Proves that a degree-at-most-d polynomial threshold function on the uniform n-dimensional Boolean cube has average sensitivity at most $8d\sqrt n$, uniformly for $1\le d\le n$. Average sensitivity counts expected output changes under single-bit flips. This establishes the asymptotic Gotsman–Linial conjecture, allowing polynomial zeros with $\mathop{\mathrm{sign}}\nolimits (0)=1$.

>>> Level Select <<<

LEVEL 1 Average sensitivity of polynomial threshold functions

released 2026-09-25 | 1 theorem · 2 lemmas · 5 proofs · 4,460 words | PLAY LEVEL 1 » (pdf)

For every n ≥ 1 and $1\le d\le n$, we prove that a polynomial threshold function of degree at most d on the uniform Boolean cube has average sensitivity at most $8d\sqrt n$. This proves the asymptotic form of the Gotsman–Linial conjecture. The bound is uniform in both parameters and uses the convention $\mathop{\mathrm{sgn}}\nolimits (0)=1$.

More Theoretical computer science Games!
Almost-linear expected-time approximation of edit distance	Superpolynomial lower bounds and quasipolynomial reconstruction from deletion traces	Polynomial-time scheduling on three identical machines	The approximation threshold for metric $k$-median
Exponential semidefinite complexity of perfect matching	A factor-two approximation for shortest common superstring	Exponential state costs for two-way automata	Fourier transforms below $n\log n$ HOT!

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