Truly Sub-quadratic Time Constant Factor Approximation of Edit Distance

23/05/2019 - 12:00

Edit distance is a 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. This distance measure finds applications in fields such as computational biology, pattern recognition, text processing, and information retrieval. The edit distance can be computed exactly using a dynamic programming algorithm that runs in quadratic time, which is also known to be almost optimal under SETH assumption [Backurs, Indyk 2015]. Andoni, Krauthgamer and Onak (2010) gave a nearly linear time (randomized) algorithm that approximates edit distance within poly-log(n) approximation factor. In this talk we discuss a randomized algorithm with running time $\tilde{O}(n^{2-2/7})$ that approximates the edit distance within a constant factor.

(based on a joint work with Das, Goldenberg, Koucky and Saks, appeared in FOCS’18)