Polylogarithmic Approximation for Edit Distance and the Asymmetric Query Complexity

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

zbMATH Keywords

samplingquery complexityedit distance

Mathematics Subject Classification ID

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 L₁
• 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