December 1, Wednesday 14:15, Room 303, Jacobs Building

Title: Polylogarithmic Approximation for Edit Distance and the Asymmetric Query Complexity

Lecturer : Robert Krauthgamer

Lecturer homepage : http://www.wisdom.weizmann.ac.il/~robi/

Affiliation : Faculty of Mathematics and Computer Science, The Weizmann Institute of Science

We present a near-linear time algorithm that approximates
the edit distance between two strings within a significantly
better factor than previously known. This result emerges in
our investigation of edit distance from a new perspective,
namely a model of asymmetric queries, for which we present
near-tight bounds.
Another consequence of this new model is the first rigorous
separation between edit distance and Ulam distance, by
tracing the hardness of edit distance to phenomena
that were not used by previous analyses.
[Joint work with Alexandr Andoni and Krzysztof Onak.]