Edit distance is a measure of similarity of two strings based

onthe minimum number of character insertions, deletions, and

substitutions required to transform one string into the other. The edit

distance can be computed exactly using a dynamic programming algorithm

that runs in quadratic time. Andoni, Krauthgamer and Onak (2010) gave a

nearly linear time algorithm that approximates edit distance within

approximation factor $\text{poly}(\log n)$. In this talk, I will

describe an algorithm with running time $\tildeO(n^{2-2/7})$ that

approximates the edit distance within a constant factor.

This is a joint work with Diptarka Chakraborty, Elazar Goldenberg,

Michal Koucky, Michael Saks