Set reconciliation with nearly optimal communication complexity

DOI10.1109/TIT.2003.815784zbMath1302.68027OpenAlexW2142423295MaRDI QIDQ3547377

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

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

Related Items (9)

The forgiving graph: a distributed data structure for low stretch under adversarial attack ⋮ Compact samples for data dissemination ⋮ Deterministic \(k\)-set structure ⋮ Hiding Secret Points Amidst Chaff ⋮ Optimal Las Vegas reduction from one-way set reconciliation to error correction ⋮ 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

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