Combinatorics Seminar

When: Sunday, April 27, 10am Where: Schreiber 309 Speaker: Robi Krauthgamer, Weizmann Institute Title: The Computational Hardness of Estimating 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).