The Taub Faculty of Computer Science Events and Talks

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 (or equivalently, into a Hamming space) with constant distortion, shown recently in [Khot-Naor, 2005] and [Krauthgamer-Rabani, 2006].

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. An immediate consequence is that even a fixed power of edit distance does not embed into L_1 with constant distortion. In contrast with previous work that relied on the Bonami-Beckner inequality, our proof requires only elementary Fourier analysis, and easily extends to special cases like permutations.

Joint work with Alex Andoni (MIT).