We show how to compute the edit distance between two strings of length $n$ up to a factor of $2^{\tilde O(\sqrt{\log n})}$ in $n^{1+o(1)}$ 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+o(1)}$ approximation [Batu-Ergun-Sahinalp'06]. Previously, approximation of $2^{\tilde O(\sqrt{\log n})}$ was known only for embedding edit distance into $L_1$ [Ostrovsky-Rabani'07], and it is not known if that embedding can be computed in less than $n^2$ time.
Joint work with Krzysztof Onak (MIT).
Copyright. All Rights Reserved.