The computational hardness of estimating edit distance

DOI10.1137/080716530MaRDI QIDQ3068638zbMATH OpenOpenAlexFDO

Authors Alexandr Andoni, Robert Krauthgamer

Publication date 17 January 2011

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL http://hdl.handle.net/1721.1/58102

zbMATH Keywords

sketchingembeddingedit distanceFourier analysiscommunication complexityUlam metric

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Algorithms on strings (68W32)

Recommendations

• Lower bounds for edit distance and product metrics via Poincaré-type inequalities
• Low distortion embeddings for edit distance
• scientific article; zbMATH DE number 7375961
• Embedding the Ulam metric into \(\ell_{1}\)
• Efficient communication protocols for deciding edit distance

Cited in

(14)

• Computation of edit probabilities and edit distances for the A5-type keystream generator
• Polylogarithmic approximation for edit distance and the asymmetric query complexity
• LCS Approximation via Embedding into Local Non-repetitive Strings
• Adaptive metric dimensionality reduction
• Low distortion embeddings for edit distance
• scientific article; zbMATH DE number 7375961 (Why is no real title available?)
• Embedding the Ulam metric into \(\ell_{1}\)
• Sketching and embedding are equivalent for norms
• Lower bounds for edit distance and product metrics via Poincaré-type inequalities
• Estimating the longest increasing sequence in polylogarithmic time
• Algorithms and Computation
• scientific article; zbMATH DE number 1445304 (Why is no real title available?)
• Bounds and estimates on the average edit distance
• Efficient communication protocols for deciding edit distance

This page was built for publication: The computational hardness of estimating edit distance

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