Polylogarithmic Approximation for Edit Distance and the Asymmetric Query Complexity

We present a near-linear time algorithm for approximating the edit distance between two strings to within a significantly better factor than previously known. This result emerges in our investigation of edit distance from a new perspective, namely a model of asymmetric queries, for which we present near-tight query complexity bounds. Another consequence of this new model is the first rigorous separation between edit distance and Ulam distance, which we obtain by tracing the hardness of edit distance back to a phenomenon that was not used before.

Joint work with Alexandr Andoni and Robert Krauthgamer.