Alexandr Andoni: Approximating Edit Distance in Near-Linear Time
Tuesday, October 13, 2020 - 4:00pm to 5:00pm
Location:
Zoom Link: https://mit.zoom.us/meeting/register/tJIlceuqrzMoGdyQJAyITXLXnN6t5C1ZEDnf
Speaker:
Alexandr Andoni
Seminar group:
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.
Joint work with Negev Shekel Nosatzki, available at https://arxiv.org/abs/2005.07678.
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 https://arxiv.org/abs/2005.07678.