Constant factor approximations to edit distance on far input pairs in nearly linear time.

Michal Kouck, Michael E. Saks

Browse the full STOC paper archive.