Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless SETH is false)
From MaRDI portal
Publication:2941488
DOI10.1145/2746539.2746612zbMath1321.68548arXiv1412.0348OpenAlexW2055693471MaRDI QIDQ2941488
Publication date: 21 August 2015
Published in: Proceedings of the forty-seventh annual ACM symposium on Theory of Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1412.0348
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 (50)
Matching Triangles and Basing Hardness on an Extremely Popular Conjecture ⋮ On the Fine Grained Complexity of Finite Automata Non-emptiness of Intersection ⋮ Graphs cannot be indexed in polynomial time for sub-quadratic time string matching, unless SETH fails ⋮ The Complexity of Problems in P Given Correlated Instances ⋮ On the Equivalence among Problems of Bounded Width ⋮ Faster All-Pairs Shortest Paths via Circuit Complexity ⋮ If the Current Clique Algorithms Are Optimal, so Is Valiant's Parser ⋮ Approximating the geometric edit distance ⋮ Co-linear chaining with overlaps and gap costs ⋮ Upper and Lower Bounds for Dynamic Data Structures on Strings ⋮ Subquadratic algorithms for succinct stable matching ⋮ Approximating Longest Common Subsequence in Linear Time: Beating the $\sqrt{{n}}$ Barrier ⋮ Unnamed Item ⋮ Sequence to graph alignment using gap-sensitive co-linear chaining ⋮ A Linear-Time n 0.4 -Approximation for Longest Common Subsequence ⋮ On the Complexity of String Matching for Graphs ⋮ Quantum bounds for 2D-grid and Dyck language ⋮ Fine-grained complexity lower bounds for problems in computer aided verification ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Why is it hard to beat \(O(n^2)\) for longest common weakly increasing subsequence? ⋮ Hardness of RNA folding problem with four symbols ⋮ A Simple Algorithm for Approximating the Text-To-Pattern Hamming Distance ⋮ Fast and Deterministic Constant Factor Approximation Algorithms for LCS Imply New Circuit Lower Bounds ⋮ Graphs cannot be indexed in polynomial time for sub-quadratic time string matching, unless SETH fails ⋮ Fine-grained Lower Bounds on Cops and Robbers ⋮ Real-valued embeddings and sketches for fast distance and similarity estimation ⋮ Optimized SAT encoding of conformance checking artefacts ⋮ Tight conditional lower bounds for longest common increasing subsequence ⋮ Near-linear time edit distance for indel channels ⋮ Unnamed Item ⋮ Locally consistent decomposition of strings with applications to edit distance sketching ⋮ Index structures for fast similarity search for symbol strings ⋮ Unnamed Item ⋮ Refining the \(r\)-index ⋮ Unnamed Item ⋮ A fine-grained analogue of schaefer's Theorem in P: dichotomy of ∃k∀-quantified first-order graph properties ⋮ Fine-Grained Complexity Theory (Tutorial) ⋮ The Orthogonal Vectors Conjecture for Branching Programs and Formulas ⋮ A Multi-labeled Tree Edit Distance for Comparing "Clonal Trees" of Tumor Progression. ⋮ Dynamic Time Warping in Strongly Subquadratic Time: Algorithms for the Low-Distance Regime and Approximate Evaluation ⋮ Computing permanents and counting Hamiltonian cycles by listing dissimilar vectors ⋮ Unnamed Item ⋮ Unnamed Item ⋮ The fine-grained complexity of multi-dimensional ordering properties ⋮ Unnamed Item
Uses Software
Cites Work
- Unnamed Item
- Ramsey partitions and proximity data structures
- On sparse spanners of weighted graphs
- Scale-oblivious metric fragmentation and the nonlinear Dvoretzky theorem
- On Approximate Distance Labels and Routing Schemes with Affine Stretch
- Distance Oracles for Unweighted Graphs: Breaking the Quadratic Barrier with Constant Additive Error
- Approximate distance oracles
- Fast Algorithms for Constructing t-Spanners and Paths with Stretch t
- Near-Linear Time Construction of Sparse Neighborhood Covers
- Shortest-path queries in static networks
- Approximate distance oracles with constant query time
- Automata, Languages and Programming
This page was built for publication: Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless SETH is false)
