Polylogarithmic Approximation for Edit Distance and the Asymmetric Query Complexity
From MaRDI portal
Publication:4933374
DOI10.1007/978-3-642-16367-8_16zbMath1309.68228arXiv1005.4033OpenAlexW2949329905MaRDI 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
Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Algorithms on strings (68W32)
Related Items
If the Current Clique Algorithms Are Optimal, so Is Valiant's Parser ⋮ Approximating the geometric edit distance ⋮ Edit Distance Cannot Be Computed in Strongly Subquadratic Time (Unless SETH is False) ⋮ Approximating Longest Common Subsequence in Linear Time: Beating the $\sqrt{{n}}$ Barrier ⋮ A Linear-Time n 0.4 -Approximation for Longest Common Subsequence ⋮ Quantum meets fine-grained complexity: sublinear time quantum algorithms for string problems ⋮ Unnamed Item ⋮ Detecting life signatures with RNA sequence similarity measures ⋮ 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 ⋮ Truly Subcubic Algorithms for Language Edit Distance and RNA Folding via Fast Bounded-Difference Min-Plus Product ⋮ Real-valued embeddings and sketches for fast distance and similarity estimation ⋮ LCS approximation via embedding into locally non-repetitive strings ⋮ Unnamed Item
Cites Work
- 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
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
