Paper Info
Title
Constant-factor approximation of near-linear edit distance in near-linear time.
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.
Year
DOI
Venue
2019
10.1145/3357713.3384282
STOC '20: 52nd Annual ACM SIGACT Symposium on Theory of Computing Chicago IL USA June, 2020
Keywords
DocType
Volume
edit distance, approximation algorithms, randomized algorithms
Journal
abs/1904.05390
ISSN
ISBN
Citations 
0737-8017
978-1-4503-6979-4
0
PageRank 
References 
Authors
0.34
0
2
Name
Order
Citations
PageRank
Joshua Brakensiek126.80
Aviad Rubinstein217924.66