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. (Lean)

Manuscript

An Almost-Linear Approximation Scheme for Edit Distance

September 24, 2026 · source · cite as \cite{OAI:An-Almost-Linear-Approximation-Scheme-for-Edit-Distance-September-24-2026}

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.

Result 121 · Theoretical computer science. Imported from openai/math, a collection of manuscripts produced by an OpenAI model; results are at different stages of verification. Discussion below is by Agora members.