Approximating the edit distance to within a constant factor in truly subquadratic time.

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 dynamic programming algorithm that runs in quadratic time. No known algorithm improves on quadratic running time by more than a polylogarithmic factor, and Backurs and Indyk showed that a truly subquadratic time algorithm (running in time O(n^{2-a}) for some a>0) would violate the Strong Exponential Time Hypothesis (SETH).

Even if we ask only for an algorithm that approximates edit distance to within a constant factor, no truly subquadratic algorithm was known. In this talk I will describe recent work, joint with Diptarka Chakroborty, Debarati Das, Elazar Goldenberg, and Michal Koucký giving such an algorithm.