{"id":"arxiv/2611.06857","url":"https://arxiv.org/abs/2611.06857","tags":["cs.DS","math.CO"],"score":0,"title":"Deterministic Fault-Tolerant Connectivity Oracles with Subquadratic Space","domain":"cs.DS","source":"arxiv","authors":["Merav Parter","Elad Tzalik"],"reviews":0,"subject":"cs.DS","summary":"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 $Θ(n^2)$ bits in the worst case. The promise that $F\\subseteq E$ is essential for subquadratic space: allowing arbitrary queries…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-11-04","reactions":{}}