Efficient communication protocols for deciding edit distance

DOI10.1007/978-3-642-33090-2_56MaRDI QIDQ2912882zbMATH OpenOpenAlexFDO

Authors Hossein Jowhari

Publication date 25 September 2012

Published in Algorithms – ESA 2012 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-33090-2_56

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Network protocols (68M12)

Recommendations

• Publication:4952617
• The computational hardness of estimating edit distance
• Low distortion embeddings for edit distance
• Streaming algorithms for embedding and computing edit distance in the low distance regime
• Approximating edit distance in near-linear time

Cited in

(7)

• Optimal Las Vegas reduction from one-way set reconciliation to error correction
• scientific article; zbMATH DE number 7559216 (Why is no real title available?)
• The computational hardness of estimating edit distance
• scientific article; zbMATH DE number 7561345 (Why is no real title available?)
• Locally consistent decomposition of strings with applications to edit distance sketching
• scientific article; zbMATH DE number 1445304 (Why is no real title available?)
• Deterministic document exchange protocols and almost optimal binary codes for edit errors

This page was built for publication: Efficient communication protocols for deciding edit distance

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