scientific article; zbMATH DE number 7375961

DOI10.4230/LIPIcs.ICALP.2018.34zbMath1499.68421arXiv1804.09907MaRDI QIDQ5002705

William Kuszmaul, Michael P. Kim, Ofir Geri, Moses Charikar

Publication date: 28 July 2021

Full work available at URL: https://arxiv.org/abs/1804.09907

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

embeddingalignmentdimension reductionapproximation algorithmsedit distance

Mathematics Subject Classification ID

Approximation algorithms (68W25) Algorithms on strings (68W32)

Related Items

Train tracks with gaps: applying the probabilistic method to trains, Dynamic Time Warping in Strongly Subquadratic Time: Algorithms for the Low-Distance Regime and Approximate Evaluation

Uses Software

• PSI-BLAST
• BLAST

Cites Work

• Unnamed Item
• Unnamed Item
• Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless SETH is false)
• The Computational Hardness of Estimating Edit Distance
• Oblivious string embeddings and edit distance approximations
• Improved lower bounds for embeddings into L₁
• Uniform Hashing in Constant Time and Optimal Space
• Algorithms on Strings, Trees and Sequences
• Incremental String Comparison
• The String-to-String Correction Problem
• Approximating Edit Distance in Near-Linear Time
• Theoretical and Practical Improvements on the RMQ-Problem, with Applications to LCA and LCE
• Streaming algorithms for embedding and computing edit distance in the low distance regime
• Low distortion embeddings for edit distance