Family 121Theoretical computer scienceNo LeanNot yet digested
Almost-linear approximation of edit distance
For every fixed rational , gives a randomized approximation to unit-cost edit distance in worst-case expected time , 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.
Manuscripts in this family · 1
An Almost-Linear Approximation Scheme for Edit Distance
Sep 24, 2026·paper.pdf
We give a uniform randomized approximation scheme for unit-cost edit distance. For every fixed rational , it estimates the distance between arbitrary explicitly stored strings of total length N within a factor with probability at least 2/3, in worst-case expected time on a logarithmic-word RAM. The algorithm supports polynomially bounded integer alphabets and returns zero deterministically on equal strings.