Michael Saks: Approximating the edit distance to within a constant factor in truly subquadratic time

Abstract: 

Edit distance is a widely used measure of similarity of two strings based on

the 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

classical discrete dynamic programming algorithm that runs in quadratic time.

The best algorithm known for exact edit distance improves on quadratic running time

by only a polylogarithmic factor.

I will describe recent work from FOCS 2018, joint with Diptarka Chakroborty, Debarati Das, Elazar

Goldenberg, and Michal Kouck\'y that gives a randomized constant factor approximation to edit distance

in time $\tilde{O}(n^{12/7})$. This is the first constant factor approximation algorithm that

runs in truly subquadratic time.