Deterministic Fault-Tolerant Connectivity Oracles with Subquadratic Space
Abstract
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⊆ E. When the number of failures is unrestricted, prior constructions exhibited a sharp contrast between randomization and determinism: randomized oracles use only Õ(n) space [Duan and Pettie, SICOMP 2020], whereas no deterministic construction was known to improve upon storing G explicitly, requiring Θ(n2) bits in the worst case. The promise that F⊆ E is essential for subquadratic space: allowing arbitrary queries F⊆ V× V forces quadratic space. For queries containing at most f failures, Khanna, Konrad, and Putterman [SODA 2027] recently constructed deterministic oracles using Õ(√fn) 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=Θ(n2). We present the first deterministic connectivity oracles with subquadratic space for failure sets of unrestricted size, using Õ(n7/4) space. We also establish the first polynomial separation between deterministic and randomized connectivity oracles, proving that every deterministic oracle requires Ω̃(n3/2) bits in the worst case. For queries containing at most f failures, we obtain deterministic connectivity oracles using Õ(f2/5n) space, improving the dependence on f in the bound of Khanna et al., and prove a lower bound of Ω̃(f1/4n) bits.
Related
- Spherical-Design Oracles for Zeroth-Order Optimisation: Deterministic, Variance-Free Gradient Estimation
- Quasi-Static Fault-Tolerant Feedback Control of a Quadrotor under Rotor Failure with Provable Safety Guarantees
- Fault-Tolerant Nonlinear Control of Robotic Manipulator Using Neural Network
- Fault-tolerant quantum processing of physical experiments
- Geometry-optimized hyperbolic codes for modular fault-tolerant quantum architectures
BibTeX
@misc{parter2026deterministic,
title = {{Deterministic Fault-Tolerant Connectivity Oracles with Subquadratic Space}},
author = {Merav Parter and Elad Tzalik},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.06857},
eprint = {2611.06857},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.06857},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Deterministic Fault-Tolerant Connectivity Oracles with Subquadratic Space
AU - Merav Parter
AU - Elad Tzalik
PY - 2026
DA - 2026/11/04
PB - arXiv
DO - 10.48550/arxiv.2611.06857
UR - https://arxiv.org/abs/2611.06857
AB - 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⊆ E. When the number of failures is unrestricted, prior constructions exhibited a sharp contrast between randomization and determinism: randomized oracles use only Õ(n) space [Duan and Pettie, SICOMP 2020], whereas no deterministic construction was known to improve upon storing G explicitly, requiring Θ(n^2) bits in the worst case. The promise that F⊆ E is essential for subquadratic space: allowing arbitrary queries F⊆ V× V forces quadratic space. For queries containing at most f failures, Khanna, Konrad, and Putterman [SODA 2027] recently constructed deterministic oracles using Õ(√fn) 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=Θ(n^2). We present the first deterministic connectivity oracles with subquadratic space for failure sets of unrestricted size, using Õ(n^7/4) space. We also establish the first polynomial separation between deterministic and randomized connectivity oracles, proving that every deterministic oracle requires Ω̃(n^3/2) bits in the worst case. For queries containing at most f failures, we obtain deterministic connectivity oracles using Õ(f^2/5n) space, improving the dependence on f in the bound of Khanna et al., and prove a lower bound of Ω̃(f^1/4n) bits.
ER -