Subpolynomial dimension reduction in L_p 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

Subpolynomial dimension reduction in $L_p$

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:	shapes, measuring stuff	Levels:	1
Category:	Convex and metric geometry	Lean version:	YES! ✔
Rate this game! 4.9 out of 5 (8,898 votes)

>>> How to Play <<<

Subpolynomial dimension reduction in L_p. For every fixed $1\lt p\lt \infty$ and distortion D > 1, every n-point subset of real L_p embeds into $\ell_p^d$ with distortion at most D and dimension $d=n^{o(1)}$, answering Naor's sublinear-dimension question for p ≠ 2. In contrast, exact embeddings require worst-case dimension $\Theta(n^2)$ when p ≠ 2.

>>> Level Select <<<

LEVEL 1 Subpolynomial dimension reduction in Lp

released 2026-09-23 | 1 theorem · 6 lemmas · 6 proofs · 6,190 words | PLAY LEVEL 1 » (pdf)

For every fixed $1\lt p\lt \infty$ and D > 1, every n-point subset of a real L_p space embeds into $\ell_p^d$ with distortion at most D and subpolynomial dimension $d=n^{o(1)}$. The target has the same exponent p, and the embedding need not be linear.

More Convex and metric geometry Games!
The optimal order of convex-body covering density	Dimension-free logarithmic Sobolev inequality for subgaussian log-concave measures	Hyperbolicity cones without semidefinite lifts	The Gaussian propeller conjecture
The Euclidean Steinitz–Bergström conjecture	A negative answer to the Lang–Plaut problem	The sharp distortion of edit distance into $\ell_1$	A counterexample to Bang's cylinder-covering bound

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