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

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

Recommendations

• scientific article; zbMATH DE number 1445304
• 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

(8)

• The computational hardness of estimating edit distance
• scientific article; zbMATH DE number 1303569 (Why is no real title available?)
• scientific article; zbMATH DE number 1445304 (Why is no real title available?)
• The one-way communication complexity of dynamic time warping distance
• Sketching, streaming, and fine-grained complexity of (weighted) LCS
• Optimal Las Vegas reduction from one-way set reconciliation to error correction
• Locally consistent decomposition of strings with applications to edit distance sketching
• 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)