Mike Saks, Rutgers University

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 fastest known algorithm improves on quadratic running time by more than a polylogarithmic factor. I will describe recent work, joint with Diptarka Chakroborty, Debarati Das, Elazar Goldenberg, and Michal Kouck'y  giving the first algorithm that runs in time O(n^{2-a}) for some constant a>0, (where n is the sum of the lengths of the input strings) and outputs an upper bound on edit distance that with high probability (over the randomness of the algorithm) is within a constant factor of the edit distance.