TIME: 1:30-2:20 pm,  May 13, 2008

PLACE: CSE 503  

SPEAKER: Robert Krauthgamer
         Weizmann Institute and IBM Almaden

TITLE: Lower Bounds for Edit Distance

ABSTRACT:

The edit distance between two strings is defined as the number of
insertions/deletions/substitutions needed to transform one string into
the other. This distance plays a key role in several fields like
computational biology and text processing.

Edit distance appears to be notoriously difficult to deal with
algorithmically (both theoretically and in practice). However, no
nontrivial computational lower bounds for it are known, and the only
negative evidence known is that edit distance does not embed into L_1
with constant distortion.

I will describe strong lower bounds on the communication complexity of
estimating (approximating) the edit distance. These new results
provide the first separation between Hamming distance and edit
distance in a computational setting. This bound immediately implies
non-embeddability results into L_1 or squared-L_2.

Joint work with Alex Andoni (MIT).