Seminar of Theoretical Computer Science - Askar Gafurov (14.12.2018)

Friday 14.12.2018 at 11:00, Lecture room M/213

13. 12. 2018 07.52 hod.
By: Rastislav Královič

Askar Gafurov:
Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless SETH is false)

Abstract:
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 distance between two strings is a classical computational task, with a well-known algorithm based on dynamic programming. Unfortunately, all known algorithms for this problem run in nearly quadratic time.

In this seminar, we will present the results of Backurs and Indyk (2015), who have shown that there is no exact algorithm with running complexity O(n^(2-e)) unless the Strong Exponential Time Hypothesis (SETH) is false.

Original paper: Backurs, Arturs, and Piotr Indyk. "Edit distance cannot be computed in strongly subquadratic time (unless SETH is false)." Proceedings of the forty-seventh annual ACM symposium on Theory of computing. ACM, 2015.

web: http://kedrigern.dcs.fmph.uniba.sk/STI2
rss: http://kedrigern.dcs.fmph.uniba.sk/STI2/rss.php