Efficient communication protocols for deciding edit distance

DOI10.1007/978-3-642-33090-2_56zbMATH Open1365.68284OpenAlexW131559419MaRDI QIDQ2912882FDOQ2912882

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

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

Mathematics Subject Classification ID

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

Cited In (7)

• Title not available (Why is that?)
• The computational hardness of estimating edit distance
• Title not available (Why is that?)
• Locally consistent decomposition of strings with applications to edit distance sketching
• Title not available (Why is that?)
• Deterministic document exchange protocols and almost optimal binary codes for edit errors
• Optimal Las Vegas reduction from one-way set reconciliation to error correction

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)