Seminar Details
Approximating Edit Distance in Near-Linear Time
- Start Date: March 3, 2021
- Event Start Time: 11:00 AM
- Event End Time: 12:00 PM
- Seminar Series: Theoretical Computer Science Seminar
- Presenter(s): Alexandr Andoni - Columbia University
- Event Location: Online Event
- Event Additional Info: <p>Location: The Theory of Computing Seminar is being held online. Contact the organizers for the link to the seminar. </p> <p> </p> <p>See: <a href="https://sites.google.com/view/dimacs-theory-seminar/home">https://sites.google.com/view/dimacs-theory-seminar/home</a></p> <p> </p>
- Presentation Type: Stand Alone Presentation
- Abstract:
Edit distance is a classic measure of similarity between strings, with
applications ranging from computational biology to coding. Computing
edit distance is also a classic dynamic programming problem, with a
quadratic run-time solution, often taught in the "Intro to Algorithms"
classes. Improving this runtime has been a decades-old challenge, now
ruled likely-impossible using tools from the modern area of
fine-grained complexity.
We show how to approximate the edit distance between two strings in
near-linear time, up to a constant factor. Our result completes a
research direction set forth in the breakthrough paper of
[Chakraborty, Das, Goldenberg, Koucky, Saks; FOCS'18], who showed
the first constant-factor approximation algorithm with a (strongly)
sub-quadratic running time.