Alexandr Andoni, Columbia University

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.

Location: The Theory of Computing Seminar is being held online. Contact the organizers for the link to the seminar. 

See: https://sites.google.com/view/dimacs-theory-seminar/home