Algorithms and Complexity Seminar

Approximating Edit Distance in Near-Linear Time

Alexandr Andoni (MIT)


We show how to compute the edit distance between two strings of length n up to a factor of 2^{O~(\sqrt{\log n})} in near-linear time. This is the first sub-polynomial approximation algorithm for this problem that runs in near-linear time, improving on the state-of-the-art ~n^{1/3} approximation of [Batu-Ergun-Sahinalp'06]. Previously, approximation of the same form was known only for embedding edit distance into L_1 [Ostrovsky-Rabani'05], and it is not known if that embedding can be computed in sub-quadratic time.

Joint work with Krzysztof Onak (MIT).