Polylogarithmic Approximation for Edit Distance and the Asymmetric Query Complexity.

Alexandr Andoni, Robert Krauthgamer, Krzysztof Onak

Browse the full FOCS paper archive.