### 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

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.]