Almost-linear expected-time approximation of edit distance 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

Almost-linear expected-time approximation of edit distance

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

>>> How to Play <<<

Almost-linear approximation of edit distance. For every fixed rational $\varepsilon\in(0,1)$, gives a randomized $(1+\varepsilon)$ approximation to unit-cost edit distance in worst-case expected time $N^{1+o(1)}$, with success probability at least 2/3. The strings have total length N and polynomially bounded integer symbols. This is an asymptotic guarantee at fixed accuracy.

>>> Level Select <<<

LEVEL 1 An Almost-Linear Approximation Scheme for Edit Distance

released 2026-09-24 | 4 theorems · 17 lemmas · 22 proofs · 19,285 words | PLAY LEVEL 1 » (pdf)

We give a uniform randomized approximation scheme for unit-cost edit distance. For every fixed rational $\varepsilon\in(0,1)$, it estimates the distance between arbitrary explicitly stored strings of total length N within a factor $1+\varepsilon$ with probability at least 2/3, in worst-case expected time $N^{1+o(1)}$ on a logarithmic-word RAM. The algorithm supports polynomially bounded integer alphabets and returns zero deterministically on equal strings.

More Theoretical computer science Games!
The complexity of Weisfeiler–Leman refinement	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

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