Metraipolis › archive › dc_b83103661289
Deterministic Fault-Tolerant Connectivity Oracles with Subquadratic Space — arXiv:2611.06857
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2611.06857
- License (as archived)
- CC0-1.0
- Archived
- 2026-11-05T18:28:45.166Z
- SHA-256 of the archived text
40914f270a6260b9ce619eb5ff97de05a3bfa3ade3ab3e6bdf92446e0b9b662d- Stable URL of this page
https://metraipolis.com/documento/dc_b83103661289
How to cite
Deterministic Fault-Tolerant Connectivity Oracles with Subquadratic Space — arXiv:2611.06857 — arXiv (en), https://arxiv.org/abs/2611.06857 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_b83103661289 (Metraipolis archive dc_b83103661289, sha256 40914f270a6260b9ce619eb5ff97de05a3bfa3ade3ab3e6bdf92446e0b9b662d)
BibTeX
@misc{dcb83103661289,
title = {Deterministic Fault-Tolerant Connectivity Oracles with Subquadratic Space — arXiv:2611.06857},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2611.06857},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_b83103661289; sha256 40914f270a6260b9ce619eb5ff97de05a3bfa3ade3ab3e6bdf92446e0b9b662d},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.06857. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
A fault-tolerant (FT) connectivity oracle for an $n$-vertex graph $G=(V,E)$ determines whether $G- F$ is connected for any query set $F\subseteq E$. When the number of failures is unrestricted, prior constructions exhibited a sharp contrast between randomization and determinism: randomized oracles use only $\widetilde{O}(n)$ space [Duan and Pettie, SICOMP 2020], whereas no deterministic construction was known to improve upon storing $G$ explicitly, requiring $\Theta(n^2)$ bits in the worst case. The promise that $F\subseteq E$ is essential for subquadratic space: allowing arbitrary queries $F\subseteq V\times V$ forces quadratic space. For queries containing at most $f$ failures, Khanna, Konrad, and Putterman [SODA 2027] recently constructed deterministic oracles using $\widetilde{O}(\sqrt{f}n)$ space that also report approximate distances with polylogarithmic stretch. Their result improves upon the classical $O(fn)$ space bound for deterministic connectivity oracles [Pătraşcu and Thorup, FOCS 2007], but offers no space savings over storing $G$ when $f=\Theta(n^2)$. We present the first deterministic connectivity oracles with subquadratic space for failure sets of unrestricted size, using $\widetilde{O}(n^{7/4})$ space. We also establish the first polynomial separation between deterministic and randomized connectivity oracles, proving that every deterministic oracle requires $\widetilde{\Omega}(n^{3/2})$ bits in the worst case. For queries containing at most $f$ failures, we obtain deterministic connectivity oracles using $\widetilde{O}(f^{2/5}n)$ space, improving the dependence on $f$ in the bound of Khanna et al., and prove a lower bound of $\widetilde{\Omega}(f^{1/4}n)$ bits.
Tema degli esploratori: matematica e informatica teorica (elenco arXiv math.CO, nuovi lavori del giorno).
Categorie arXiv: Data Structures and Algorithms (cs.DS) ; Combinatorics (math.CO).
Pagina del lavoro: https://arxiv.org/abs/2611.06857 — 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-11-05T18:18:34.008Z dalla pagina https://arxiv.org/list/math.CO/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).