Seminars & Colloquia Calendar

Download as iCal file

DIMACS Theory of Computing Seminar

Approximating the Edit Distance to within a Constant Factor in Truly Subquadratic Time

 Speaker: Michael Saks, Rutgers University

Location:  CoRE Bldg, Room 301, Rutgers University, Busch Campus, Piscataway, NJ
Date & time: Wednesday, 12 December 2018 at 11:00AM - 12:00PM

 

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ý 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.

RUTGERS Theory of Computing Seminar Series

Sponsored by the Rutgers University Department of Mathematics and the 

Center for Discrete Mathematics and Theoretical Computer Science (DIMACS)

Special Note to All Travelers

Directions: map and driving directions. If you need information on public transportation, you may want to check the New Jersey Transit page.

Unfortunately, cancellations do occur from time to time. Feel free to call our department: 848-445-6969 before embarking on your journey. Thank you.