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.