Automated, no-frills recording service for CSAIL research talks

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 1092 times

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