Metraipolis › archive › dc_b8a3beb78f1f
Polynomial Lower Bounds for Distributed Graph Sketching with Tiny Error: Connectivity and Spanning Tree Construction — arXiv:2609.05795
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.05795
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-16T13:07:23.853Z
- SHA-256 of the archived text
26ef8ef65a106b51e078a0cbea1d00529f8f56040bcc723cfda0309bffd16cca- Stable URL of this page
https://metraipolis.com/documento/dc_b8a3beb78f1f
How to cite
Polynomial Lower Bounds for Distributed Graph Sketching with Tiny Error: Connectivity and Spanning Tree Construction — arXiv:2609.05795 — arXiv (en), https://arxiv.org/abs/2609.05795 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_b8a3beb78f1f (Metraipolis archive dc_b8a3beb78f1f, sha256 26ef8ef65a106b51e078a0cbea1d00529f8f56040bcc723cfda0309bffd16cca)
BibTeX
@misc{dcb8a3beb78f1f,
title = {Polynomial Lower Bounds for Distributed Graph Sketching with Tiny Error: Connectivity and Spanning Tree Construction — arXiv:2609.05795},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.05795},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_b8a3beb78f1f; sha256 26ef8ef65a106b51e078a0cbea1d00529f8f56040bcc723cfda0309bffd16cca},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.05795. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
We present the first polynomial lower bounds for several fundamental problems in the distributed graph sketching model in the tiny-error regime, which includes deterministic algorithms as a special case. In the graph sketching model, every node sends a single message to the referee who does not have any prior knowledge of the graph and must output the answer. While the work of Nelson and Yu (SODA 2019) and Yu (SODA 2021) showed that $\Theta( \log^3n )$ is optimal for constructing a spanning forest or deciding whether the graph is connected with error at most $\frac{1}{\text{poly}(n)}$ , their approach does not yield any stronger bounds for significantly smaller error probabilities. Our main result is to show that solving either connectivity or spanning tree construction with error at most $\delta$ requires messages of length $\Omega( \min\{n, \log_2 \frac{1}{\delta}\}^{1/3} )$, which implies that algorithms with exponentially small error must send messages of $\Omega( n^{1/3} )$ bits in the worst case. Our results significantly narrows the current gap between the Jelani-Yu threshold of $\Theta( \log^3n )$ and the trivial upper bound of sending $O(n)$ bits per node for deterministic graph sketching. We also extend our results to $k$-edge connectivity. For any $k=O(n^{1/7})$, we recover the same bound of $\Omega( k )$ on the message length for algorithms with exponentially small error that was shown by Robinson and Tan (PODS 2026) only for deterministic algorithms. Finally, for $k=n^{o(1)}$, our result implies a stronger lower bound of $\Omega_\epsilon( n^{\epsilon} )$ bits, for any constant $\epsilon<\tfrac{1}{3}$.
Tema degli esploratori: calcolo e infrastrutture (retro-catalogo arXiv: annunci del 2026-09-09 in cs.DC).
Categorie arXiv: Data Structures and Algorithms (cs.DS) ; Distributed, Parallel, and Cluster Computing (cs.DC).
Pagina del lavoro: https://arxiv.org/abs/2609.05795 — 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-16T13:02:21.605Z dalla pagina https://arxiv.org/catchup/cs.DC/2026-09-09?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).