Approximating edit distance in near-linear time.

Alexandr Andoni, Krzysztof Onak

Browse the full STOC paper archive.