Set reconciliation with nearly optimal communication complexity

DOI10.1109/TIT.2003.815784MaRDI QIDQ3547377zbMATH OpenOpenAlexFDO

Authors Yaron M. Minsky, Ari Trachtenberg, Richard Zippel

Publication date 21 December 2008

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1109/tit.2003.815784

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10) Network protocols (68M12) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Simple multi-party set reconciliation
• Optimal Las Vegas reduction from one-way set reconciliation to error correction
• scientific article; zbMATH DE number 6297761
• Beyond set disjointness: the communication complexity of finding the intersection
• Data verification and reconciliation with generalized error-control codes

Cited in

(15)

• The forgiving graph: a distributed data structure for low stretch under adversarial attack
• Robust property-preserving hash functions for Hamming distance and more
• Multiparty cardinality testing for threshold private intersection
• Multi-party threshold private set intersection with sublinear communication
• Simple multi-party set reconciliation
• Data verification and reconciliation with generalized error-control codes
• Hiding Secret Points Amidst Chaff
• Efficient detection of discrepancies in multiple file copies
• Optimal Las Vegas reduction from one-way set reconciliation to error correction
• Better space-time-robustness trade-offs for set reconciliation
• Invertible Bloom lookup tables with less memory and randomness
• Parameterized streaming algorithms for topological sorting
• Set Reconciliation
• Compact samples for data dissemination
• Deterministic \(k\)-set structure

This page was built for publication: Set reconciliation with nearly optimal communication complexity

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