CSAIL Logo.

About This Video

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.


Viewed 136 times


Note: to download, right-click on the links below and choose "Save file as".
HD, MP4 Format
HD, WebM Format
SD, MP4 Format
SD, WebM Format

Comments