Deterministic Fault-Tolerant Connectivity Oracles with Subquadratic Space

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 O(n) space [Duan and Pettie, SICOMP 2020], whereas no deterministic construction was known to improve upon storing G explicitly, requiring Θ(n²) 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 O(√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²). We present the first deterministic connectivity oracles with subquadratic space for failure sets of unrestricted size, using O(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 O(f2/5n) space, improving the dependence on f in the bound of Khanna et al., and prove a lower bound of Ω(f1/4n) bits.