A sublinear algorithm for weakly approximating edit distance.

Tugkan Batu, Funda Ergn, Joe Kilian, Avner Magen, Sofya Raskhodnikova, Ronitt Rubinfeld, Rahul Sami

Browse the full STOC paper archive.