Alexandr Andoni: Approximating Edit Distance in Near-Linear Time

Tuesday, October 13, 2020 - 4:00pm to 5:00pm
Zoom Link:
Alexandr Andoni


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.

Joint work with Negev Shekel Nosatzki, available at