Almost-linear approximation of edit distance

What OpenAI claims

For every fixed rational ε ∈ (0,1), gives a randomized (1+ε) 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. (Lean)

Paper

1. An Almost-Linear Approximation Scheme for Edit Distance

   24 September 2026 · Preprint, not peer reviewed · PDF

   OpenAI's abstract We give a uniform randomized approximation scheme for unit-cost edit distance. For every fixed rational ε ∈ (0,1), it estimates the distance between arbitrary explicitly stored strings of total length N within a factor 1+ε 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.

Status

Preprint. The paper has not been independently reviewed. Treat the result as OpenAI's claim until other mathematicians have checked it. If a video exists, it illustrates the statement; it is not the proof.