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

DOI10.1137/15M1053128zbMath1396.68137WikidataQ129647625 ScholiaQ129647625MaRDI QIDQ4571928

Artūrs Bačkurs, Piotr Indyk

Publication date: 4 July 2018

Published in: SIAM Journal on Computing (Search for Journal in Brave)

zbMATH Keywords

pattern matchingedit distanceSETHconditional hardness

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Algorithms on strings (68W32)

Related Items (12)

Longest common subsequence in sublinear space ⋮ Absent Subsequences in Words ⋮ On the Complexity of String Matching for Graphs ⋮ Matching patterns with variables under edit distance ⋮ Unnamed Item ⋮ Near-optimal quantum algorithms for string problems ⋮ Quantum meets fine-grained complexity: sublinear time quantum algorithms for string problems ⋮ Dynamic and internal longest common substring ⋮ The Fine-Grained Complexity of Median and Center String Problems Under Edit Distance ⋮ Unnamed Item ⋮ Unnamed Item ⋮ From Circuit Complexity to Faster All-Pairs Shortest Paths

Cites Work

• Unnamed Item
• A faster algorithm computing string edit distances
• Which problems have strongly exponential complexity?
• A new algorithm for optimal 2-constraint satisfaction and its implications
• Deterministic APSP, Orthogonal Vectors, and More: Quickly Derandomizing Razborov-Smolensky
• Polylogarithmic Approximation for Edit Distance and the Asymmetric Query Complexity
• Consequences of Faster Alignment of Sequences
• Simulating branching programs with edit distance and friends: or: a polylog shaved is a lower bound made
• More Applications of the Polynomial Method to Algorithm Design
• Hardness of Easy Problems: Basing Hardness on Popular Conjectures such as the Strong Exponential Time Hypothesis (Invited Talk)
• Fast approximation algorithms for the diameter and radius of sparse graphs
• On the complexity of \(k\)-SAT

This page was built for publication: Edit Distance Cannot Be Computed in Strongly Subquadratic Time (Unless SETH is False)