We present a near-linear time algorithm that approximates the edit distance between two strings within a polylogarithmic factor. This is an exponential improvement over the previously known bounds.
Our new algorithm emerges from the investigation of the edit distance within a new framework, namely a model of asymmetric queries. Within this framework, we are able to maintain a parallel view of the upper and lower bounds, leading to near-tight query complexity bounds. Our investigation also yields the first rigorous separation between the edit distance and the Ulam distance (edit distance on permutations), thus uncovering further hardness phenomena inherent to the edit distance, beyond what the previous analyses have revealed.
I will also talk about some unfolding open questions.
Joint work with Robert Krauthgamer and Krzysztof Onak.