Approximating Edit Distance in Near-Linear Time

We show how to compute the edit distance between two strings of length n up to a factor of 2Õ(√log n) in n¹⁺ᵒ⁽¹⁾ time. This is the first subpolynomial approximation algorithm for this problem that runs in near-linear time, improving on the state-of-the-art n1/3+o(1) approximation. Previously, approximation of 2Õ(√log n) was known only for embedding edit distance into ₁, and it is not known if that embedding can be computed in less than quadratic time.