Lower bounds for embedding edit distance into normed spaces.

Alexandr Andoni, Michel Deza, Anupam Gupta, Piotr Indyk, Sofya Raskhodnikova

Browse the full SODA paper archive.