Almost Linear Size Edit Distance Sketch.

Michal Kouck, Michael E. Saks

Browse the full STOC paper archive.