Robert Krauthgamer (Weizmann Institute and IBM Almaden)
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).