Oblivious string embeddings and edit distance approximations

DOI10.1145/1109557.1109644zbMath1192.68344OpenAlexW4232943531MaRDI QIDQ3581511

Cenk Sahinalp, Funda Ergün, Tuğkan Batu

Publication date: 16 August 2010

Published in: Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm - SODA '06 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1109557.1109644

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05) Permutations, words, matrices (05A05)

Related Items (16)

Sketching and Embedding are Equivalent for Norms ⋮ Binary vectors for fast distance and similarity estimation ⋮ Approximating tree edit distance through string edit distance ⋮ Approximating Longest Common Subsequence in Linear Time: Beating the $\sqrt{{n}}$ Barrier ⋮ A Linear-Time n ^0.4 -Approximation for Longest Common Subsequence ⋮ Unnamed Item ⋮ Quantum meets fine-grained complexity: sublinear time quantum algorithms for string problems ⋮ Approximate nearest neighbor search for \(\ell_{p}\)-spaces \((2 < p < \infty)\) via embeddings ⋮ 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 ⋮ Polylogarithmic Approximation for Edit Distance and the Asymmetric Query Complexity ⋮ LCS approximation via embedding into locally non-repetitive strings ⋮ LCS Approximation via Embedding into Local Non-repetitive Strings ⋮ Dynamic Time Warping in Strongly Subquadratic Time: Algorithms for the Low-Distance Regime and Approximate Evaluation ⋮ Unnamed Item

This page was built for publication: Oblivious string embeddings and edit distance approximations