An Almost-Linear Approximation Scheme for Edit Distance
There is one uniform randomized algorithm that, given explicitly stored strings of total length over polynomially bounded integer alphabets and a rational , returns a nonnegative integer such that , with worst-case expected running time as on the logarithmic-word RAM for every fixed rational , and returns zero deterministically on equal strings.
The accuracy guarantee and running-time bound are rigorously established across Sections 2, 8, and 10, with all arithmetic, sampling, and data-structure operations explicitly charged.
“Theorem 1.1. There is one uniform randomized algorithm that, given x, y and a rational ε ∈ (0, 1), returns a nonnegative integer Db such that Pr[ED(x, y) ≤ Db ≤ (1 + ε) ED(x, y)] ≥ 2/3. For every fixed rational ε, its worst-case expected running time on strings of total length N is N1+o(1) as N → ∞ on the logarithmic-word RAM. The expectation is over internal randomness only, and the bound includes input processing, preprocessing, numerical work, random sampling and all data-structure operations. Equal strings return zero deterministically.” · Show in paper