Title: On embedding edit distance into L_1
Robert Krauthgmaer [IBM Almaden]

Abstract:

The edit distance (aka Levenshtein distance) between two strings is the
number of character insertions, deletions and substitutions required to
transform one string to the other. A very powerful paradigm for solving
computational problems on the metric space induced by the edit distance
is to embed this metric into L_1, using a low-distortion map (if possible).

I will first present a low-distortion embedding of edit distance on
permutations (aka the Ulam metric) [based on joint work (i) with Moses
Charikar, and (ii) with Parikshit Gopalan and T.S. Jayram]. I will then
show a lower bound on the distortion required to embed all 0-1 strings
[joint work with Yuval Rabani].