A sublinear algorithm for weakly approximating edit distance

DOI10.1145/780542.780590MaRDI QIDQ3581249zbMATH OpenOpenAlexFDO

Authors Tuğkan Batu, Funda Ergün, Joe Kilian, Avner Magen, Sofya Raskhodnikova, Ronitt Rubinfeld, Rahul Sami

Publication date 16 August 2010

Published in Proceedings of the thirty-fifth annual ACM symposium on Theory of computing (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25)

Recommendations

• Approximating edit distance in near-linear time
• Approximating edit distance in near-linear time
• Near-optimal sublinear time algorithms for Ulam distance
• Approximating Edit Distance Within Constant Factor in Truly Sub-quadratic Time
• Efficiently approximating edit distance between pseudorandom strings

Cited in

(29)

• Surprises in approximating Levenshtein distances
• Nonembeddability theorems via Fourier analysis
• Tolerant property testing and distance approximation
• Lower bounding edit distances between permutations
• Edit Distance to Monotonicity in Sliding Windows
• Approximate membership for regular languages modulo the edit distance
• Approximating edit distance in truly subquadratic time: quantum and MapReduce
• Approximating edit distance in near-linear time
• Polylogarithmic approximation for edit distance and the asymmetric query complexity
• Approximating Edit Distance in Truly Subquadratic Time: Quantum and MapReduce
• Approximating Edit Distance Within Constant Factor in Truly Sub-quadratic Time
• Quantum pattern matching fast on average
• Constant-factor approximation of near-linear edit distance in near-linear time
• Approximating edit distance in near-linear time
• Efficiently approximating edit distance between pseudorandom strings
• Near-optimal sublinear time algorithms for Ulam distance
• Testing permutation properties through subpermutations
• The intractability of computing the Hamming distance
• A Linear-Time n ^0.4 -Approximation for Longest Common Subsequence
• Indexed dynamic programming to boost edit distance and LCSS computation
• Near-linear time edit distance for indel channels
• Weighted edit distance computation: strings, trees, and Dyck
• Testing versus estimation of graph properties, revisited
• The power and limitations of uniform samples in testing properties of figures
• Approximation algorithms for LCS and LIS with truly improved running times
• A linear-time \(n^{0.4}\)-approximation for longest common subsequence
• Many flavors of edit distance
• Edit distance in near-linear time: it's a constant factor
• Let's try to be more tolerant: on tolerant property testing and distance approximation (invited talk)

This page was built for publication: A sublinear algorithm for weakly approximating edit distance

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3581249)