Seminár z teoretickej informatiky - Askar Gafurov (14.12.2018)

v piatok 14.12.2018 o 11:00 hod. v miestnosti M/213

13. 12. 2018 07.46 hod.
Od: Rastislav Královič

Prednášajúci: Askar Gafurov

Názov: Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless SETH is false)

Termín: 14.12.2018, 11:00 hod., M/213

Abstrakt:
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