Edit Distance in Near-Linear Time: it's a Constant Factor.

Alexandr Andoni, Negev Shekel Nosatzki

Browse the full FOCS paper archive.