Edit Distance Cannot Be Computed in Strongly Subquadratic Time (Unless SETH is False)

© 2018 Society for Industrial and Applied Mathematics. The edit distance (a.k.a. the Levenshtein distance) between two strings is defined as the minimum number of insertions, deletions, or substitutions of symbols needed to transform one string into another. The problem of computing the edit distanc...

Full description

Bibliographic Details
Main Authors: Backurs, Arturs, Indyk, Piotr
Other Authors: Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory
Format: Article
Language:English
Published: Society for Industrial & Applied Mathematics (SIAM) 2021
Subjects:
Online Access:https://hdl.handle.net/1721.1/137586