The computational hardness of estimating edit distance

DOI10.1137/080716530zbMATH Open1213.68305OpenAlexW2169838205MaRDI QIDQ3068638FDOQ3068638

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

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

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)

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
• Title not available (Why is that?)
• 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
• Title not available (Why is that?)
• 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)