Polylogarithmic Approximation for Edit Distance and the Asymmetric Query Complexity
From MaRDI portal
Publication:4933374
DOI10.1007/978-3-642-16367-8_16zbMath1309.68228arXiv1005.4033MaRDI QIDQ4933374
Robert Krauthgamer, Alexandr Andoni, Krzysztof Onak
Publication date: 12 October 2010
Published in: Property Testing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1005.4033
68Q25: Analysis of algorithms and problem complexity
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68W25: Approximation algorithms
68W32: Algorithms on strings
Related Items
Unnamed Item, If the Current Clique Algorithms Are Optimal, so Is Valiant's Parser, Edit Distance Cannot Be Computed in Strongly Subquadratic Time (Unless SETH is False), Truly Subcubic Algorithms for Language Edit Distance and RNA Folding via Fast Bounded-Difference Min-Plus Product, Approximating Longest Common Subsequence in Linear Time: Beating the $\sqrt{{n}}$ Barrier, Fast and Deterministic Constant Factor Approximation Algorithms for LCS Imply New Circuit Lower Bounds, A Simple Algorithm for Approximating the Text-To-Pattern Hamming Distance, Unnamed Item, A Linear-Time n 0.4 -Approximation for Longest Common Subsequence, Real-valued embeddings and sketches for fast distance and similarity estimation, LCS approximation via embedding into locally non-repetitive strings, Detecting life signatures with RNA sequence similarity measures, Approximating the geometric edit distance, Quantum meets fine-grained complexity: sublinear time quantum algorithms for string problems
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A faster algorithm computing string edit distances
- Spot-checkers
- Fast and compact regular expression matching
- Nonembeddability theorems via Fourier analysis
- The Computational Hardness of Estimating Edit Distance
- Approximate nearest neighbors and sequence comparison with block operations
- Space lower bounds for distance approximation in the data stream model
- A sublinear algorithm for weakly approximating edit distance
- Optimal approximations of the frequency moments of data streams
- Oblivious string embeddings and edit distance approximations
- Improved lower bounds for embeddings into L1
- Algorithms on Strings, Trees and Sequences
- Incremental String Comparison
- The String-to-String Correction Problem
- Efficient Search for Approximate Nearest Neighbor in High Dimensional Spaces
- Approximating edit distance in near-linear time
- Estimating the distance to a monotone function
- Low distortion embeddings for edit distance
