Title: Query Complexity of Edit Distance

Speaker: Alex Andoni, Princeton 

Abstract: 

We study the query complexity of estimating the edit distance between two
strings.  In our setting, the algorithm knows one string entirely, and has
only query access to the other string.  The goal is to
approximate the edit distance between the two strings using a small number
of queries.  We give both upper and lower bounds for this
problem, and show they are near-tight in at least one regime of the
approximation factor.

Our work has the following further implications.  The upper bound
leads to the first polylogarithmic factor approximation for computing edit
distance in near-linear time, for strings at large distances.

Our lower bound implies that estimating edit distance between two
highly repetitive strings requires provably higher complexity than in the
case of non-repetitive strings (Ulam distance).  Specifically, while the
Ulam distance can be approximated within a constant factor using only a
logarithmic number of queries, we show that the same
problem under general edit distance requires an almost polynomial
number of queries.  To the best of our knowledge, this is the first such
separation, in any computational model.

Joint work with Robert Krauthgamer (Weizmann Inst), and Krzysztof Onak
(MIT).