Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless SETH is false)
作者： Arturs Backurs , Piotr Indyk
关键词: Combinatorics 、 Levenshtein distance 、 Discrete mathematics 、 Edit distance 、 Approximate string matching 、 String-to-string correction problem 、 3SUM 、 Jaro–Winkler distance 、 Mathematics 、 Damerau–Levenshtein distance 、 Wagner–Fischer algorithm
摘要: … The problem of computing the edit distance between two strings is a classical computational … of computing edit distance might be tight. Specifically, we show that, if the edit distance can …
arxiv.org
harvard.edu
acm.org
core.ac.uk 
sci-hub.se 参考文章(14)
Arturs Backurs, Virginia Vassilevska Williams, Amir Abboud, Quadratic-Time Hardness of LCS and other Sequence Similarity Measures arXiv: Computational Complexity. ,(2015)
Russell Impagliazzo, Ramamohan Paturi, On the complexity of K -SAT conference on computational complexity. ,vol. 62, pp. 367- 375 ,(2001) , 10.1006/JCSS.2000.1727
Russell Impagliazzo, Ramamohan Paturi, Francis Zane, Which Problems Have Strongly Exponential Complexity Journal of Computer and System Sciences. ,vol. 63, pp. 512- 530 ,(2001) , 10.1006/JCSS.2001.1774
Gonzalo Navarro, A guided tour to approximate string matching ACM Computing Surveys. ,vol. 33, pp. 31- 88 ,(2001) , 10.1145/375360.375365
William J. Masek, Michael S. Paterson, A faster algorithm computing string edit distances Journal of Computer and System Sciences. ,vol. 20, pp. 18- 31 ,(1980) , 10.1016/0022-0000(80)90002-1
Mihai Pătraşcu, Ryan Williams, On the possibility of faster SAT algorithms symposium on discrete algorithms. pp. 1065- 1075 ,(2010) , 10.5555/1873601.1873687
Alexandr Andoni, Robert Krauthgamer, Krzysztof Onak, Polylogarithmic Approximation for Edit Distance and the Asymmetric Query Complexity 2010 IEEE 51st Annual Symposium on Foundations of Computer Science. pp. 244- 252 ,(2010) , 10.1109/FOCS.2010.43
Liam Roditty, Virginia Vassilevska Williams, Fast approximation algorithms for the diameter and radius of sparse graphs Proceedings of the 45th annual ACM symposium on Symposium on theory of computing - STOC '13. pp. 515- 524 ,(2013) , 10.1145/2488608.2488673
Ryan Williams, A new algorithm for optimal 2-constraint satisfaction and its implications Theoretical Computer Science. ,vol. 348, pp. 357- 365 ,(2005) , 10.1016/J.TCS.2005.09.023
Karl Bringmann, Why Walking the Dog Takes Time: Frechet Distance Has No Strongly Subquadratic Algorithms Unless SETH Fails 2014 IEEE 55th Annual Symposium on Foundations of Computer Science. pp. 661- 670 ,(2014) , 10.1109/FOCS.2014.76