Metraipolis › archive › dc_d01e097a93ff

Toward Optimal Time-Space Tradeoffs for Set Reconciliation — arXiv:2609.14442

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.14442
License (as archived)
CC0-1.0
Archived
2026-10-16T02:15:21.572Z
SHA-256 of the archived text
9338f1a8796dacb5c9b77a43c67cac34d5a97513a982818e53142e7859484ecc
Stable URL of this page
https://metraipolis.com/documento/dc_d01e097a93ff

How to cite

Toward Optimal Time-Space Tradeoffs for Set Reconciliation — arXiv:2609.14442 — arXiv (en), https://arxiv.org/abs/2609.14442 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_d01e097a93ff (Metraipolis archive dc_d01e097a93ff, sha256 9338f1a8796dacb5c9b77a43c67cac34d5a97513a982818e53142e7859484ecc)
BibTeX
@misc{dcd01e097a93ff,
  title = {Toward Optimal Time-Space Tradeoffs for Set Reconciliation — arXiv:2609.14442},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.14442},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_d01e097a93ff; sha256 9338f1a8796dacb5c9b77a43c67cac34d5a97513a982818e53142e7859484ecc},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.14442. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

Set reconciliation, where two parties each holding a large set of elements aim to identify their set difference, is a fundamental task in many areas. Time (computation cost) and space (communication cost) are two important metrics in this problem, and much existing work optimizes one at the expense of the other, creating a clear trade-off. We study this trade-off through algorithmic upper bounds and matching space lower bounds. On one side, we propose XYZ-Sketch. For sufficiently large $d$, XYZ-Sketch achieves high-probability reconciliation for sets whose differing elements are uniformly random, using only $(1+\varepsilon)d$ elements for communication, while achieving $O(\log(1/\varepsilon))$ insertion time and expected $O(d\log V\log^{3/2}(1/\varepsilon))$ decoding time, where $d$ and $V$ denote the size of the difference between two sets and the universe size, respectively. On the other side, we establish a broad fixed-support canonical model and prove a matching space lower bound, establishing the asymptotic optimality of XYZ-Sketch. Our proof also establishes an extremality theorem resolving Walzer's conjecture. Experiments demonstrate the practical advantages of XYZ-Sketch, and the source code is available at this https URL .

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-15 in cs.DS).
Categorie arXiv: Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2609.14442 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-16T01:54:07.123Z dalla pagina https://arxiv.org/catchup/cs.DS/2026-09-15?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).