{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreienu77d7gucyxjzlfucmujcgjebgqht37d2ka3k5mk7ntcez232i4",
    "uri": "at://did:plc:3fychdutjjusoqeq24ljch6q/app.bsky.feed.post/3mhz22dtmk4n2"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2603.24530v1",
  "publishedAt": "2026-03-26T00:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "Sanjeev Khanna",
    "Christian Konrad",
    "Aaron Putterman"
  ],
  "textContent": "**Authors:** Sanjeev Khanna, Christian Konrad, Aaron Putterman\n\nFault-tolerant spanners are fundamental objects that preserve distances in graphs even under edge failures. A long line of work culminating in Bodwin, Dinitz, Robelle (SODA 2022) gives $(2k-1)$-stretch, $f$-fault-tolerant spanners with $O(k^2 f^{\\frac{1}{2}-\\frac{1}{2k}} n^{1+\\frac{1}{k}} + k f n)$ edges for any odd $k$. For any $k = \\tilde{O}(1)$, this bound is essentially optimal for deterministic spanners in part due to a known folklore lower bound that \\emph{any} $f$-fault-tolerant spanner requires $Ω(nf)$ edges in the worst case. For $f \\geq n$, this $Ω(nf)$ barrier means that any $f$-fault tolerant spanners are trivial in size. Crucially however, this folklore lower bound exploits that the spanner \\emph{is itself a subgraph}. It does not rule out distance-reporting data structures that may not be subgraphs. This leads to our central question: can one beat the $n \\cdot f$ barrier with fault-tolerant distance oracles? We give a strong affirmative answer to this question. As our first contribution, we construct $f$-fault-tolerant distance oracles with stretch $O(\\log(n)\\log\\log(n))$ that require only $\\widetilde{O}(n\\sqrt{f})$ bits of space; substantially below the spanner barrier of $n \\cdot f$. Beyond this, in the regime $n \\leq f \\leq n^{3/2}$ we show that by using our new \\emph{high-degree, low-diameter} decomposition in combination with tools from sparse recovery, we can even obtain stretch $7$ distance oracles in space $\\widetilde{O}(n^{3/2}f^{1/3})$ bits. We also show that our techniques are sufficiently general to yield randomized sketches for fault-tolerant ``oblivious'' spanners and fault-tolerant deterministic distance oracles in bounded-deletion streams, with space below the $nf$ barrier in both settings.",
  "title": "Fault-Tolerant Distance Oracles Below the $n \\cdot f$ Barrier"
}