Constant-factor approximation of near-linear edit distance in near-linear time

22/06/2020

Constant-factor approximation of near-linear edit distance in near-linear time

Joshua Brakensiek, Aviad Rubinstein

Keywords: edit distance, randomized algorithms, approximation algorithms

Abstract: We show that the edit distance between two strings of length n can be computed via a randomized algorithm within a factor of f(є) in n1+є time as long as the edit distance is at least n1−δ for some δ(є) > 0.

STOC

This is an embedded video. Talk and the respective paper are published at STOC 2020 virtual conference. If you are one of the authors of the paper and want to manage your upload, see the question "My papertalk has been externally embedded..." in the FAQ section.

Comments

Post Comment

no comments yet