A Tight Space Lower Bound for Pivot-Based Distance Oracles
summary
The gist
An approximate distance oracle (ADO) with O(1) query time can be shown to require superlinear space for sparse graphs under the Erd˝os girth conjecture…
In short
The paper investigates approximate distance oracles (ADOs) that use pivots to estimate distances, focusing on sparse graphs under the Erdős girth conjecture. It proves a tight lower bound for pivot-based 1-hop ADOs with stretch k: $\Omega(m^{1+2/(k+1)})$. This result matches existing upper bounds and shows that achieving $O(1)$ query time requires superlinear space for sparse graphs.
Key concepts
- Approximate Distance Oracle (ADO)
- An ADO is a compact data structure designed to answer distance queries within a multiplicative stretch k. It provides an approximate answer rather than the exact shortest path distance, trading accuracy for space efficiency. The paper specifically examines pivot-based ADOs where distances are estimated using stored pivot-to-pivot distances.
- Pivot-Based 1-Hop ADO
- This specific type of oracle uses a small set of 'pivots' associated with vertices to estimate distances. For example, to find the distance between two vertices $u$ and $v$, it finds their respective pivots ($p_u$ and $p_v$) and estimates the path length as $u o p_u o p_v o v$, using a pre-stored distance between the pivots.
- Stretch-Space Trade-off
- This refers to the relationship between how much error (stretch k) an oracle allows and how much memory (space) it requires. The paper shows that for pivot-based ADOs, this trade-off is optimal under the Erdős girth conjecture, establishing a specific lower bound on space required for a given stretch k.
Terminology used across episodes
This episode discusses
- A Tight Space Lower Bound for Pivot-Based Distance Oracles · Paper Radio
- On the Space Usage of Approximate Distance Oracles with Sub-2 Stretch
The paper
A Tight Space Lower Bound for Pivot-Based Distance Oracles · Read on arXiv
Department of Computer Science, Bar-Ilan University
An approximate distance oracle (ADO) is a compact data structure that answers distance queries within a multiplicative stretch k. The classical oracle of Thorup and Zwick [STOC'01, JACM'05] has stretch k=2-1 and uses O(n 1+1/) space, for every integer at least1, and this trade-off is optimal for dense graphs under the Erdős girth conjecture. However, for sparse graphs (m=O(n)), their lower bound yields nothing beyond Ω(m) space. A pivot-based 1-hop ADO gives every vertex O tilde(1) pivots and returns as an estimate the length of a walk of the form u to p u to p v to v, where p u is a pivot of u, p v is a pivot of v, and p u to p v is a stored distance. We observe that all the state-of-the-art ADOs with O tilde(1) query time are in fact pivot-based 1-hop ADOs. Our main result is that, under the Erdős girth conjecture for graphs with constant degree, there are sparse graphs on which every pivot-based 1-hop ADO with stretch k requires Ω(m 1+2/(k+1)) space, for every real k at least1. This matches the best known upper bounds with O tilde(1) query time, up to polylogarithmic factors, at every stretch where they are known. We also extend our lower bound to pivot-based ADOs with any constant number β of hops, showing that they require Ω(m 1+2/(β(k+1))) space. In addition, we obtain a tight lower bound for two-hop hopsets. Under the Erdős girth conjecture, for every integer at least3, (2-3,2) -hopsets on sparse graphs require size Ω(m 1+1/), which matches a construction based on the oracles of [Kadria and Roditty, ISAAC'25]. Using the recent explicit high-girth graphs of Double Agent [doubleAI'26], we also obtain unconditional versions of our ADO lower bounds, with the exponent above 1 multiplied by 4/5.
Transcript
Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.
Tom: We're looking at the paper: "A Tight Space Lower Bound for Pivot-Based Distance Oracles".
Jane: Here's the gist of the paper. An approximate distance oracle (ADO) with O(1) query time can be shown to require superlinear space for sparse graphs under the Erd˝os girth conjecture, matching known stretch-space trade-offs <ref:2610.29624#pg2>.
Tom: The Core Result on Pivot Oracles The main result establishes a lower bound for pivot-based 1-hop ADOs under the Erd˝os girth conjecture for constant-degree graphs, showing that every such oracle with real stretch k ≥ 1 requires space of sizeomega(e m(1+2/(k+1))).
Jane: This lower bound matches the best known upper bounds with O˜(1) query time at every stretch where the trade-off is attained, up to polylogarithmic factors.
Tom: The authors also extend this to pivot-based ADOs with any constant number β of hops, requiring space of sizeomega(e m(1+2/(β(k+1)))).
Paper summary: Tom: So, we're looking at this paper called "A Tight Space Lower Bound for Pivot-Based Distance Oracles." Basically, the authors are talking about these approximate distance oracles, ADOs. They want to know how much space you need to store so you can answer distance queries within a certain stretch k, which is like if you ask for the distance between two points and get an estimate that's at most k times the real distance.
Jane: That sounds like a lot of machinery, Tom, but the core idea seems to be about balancing that stretch factor k with how much memory you use. The paper focuses on ADOs with constant query time for sparse graphs, where the number of edges m is around n.
Lu: Right. They start by looking at a specific type of oracle called a pivot-based one-hop ADO <ref:2610.29624#pg1,a pivot-based 1-hop ADO>. This structure gives every vertex, every vertex, a pivot point and returns an estimate based on those pivots and stored distances between them.
Meng: I'm wondering what that means practically for me when I'm deploying this stuff. If we have these ADOs with constant query time, the paper claims there are sparse graphs where you need space that grows faster than just linear in the number of edges m.
Tom: Exactly. The main claim is that under a certain conjecture—the Erdős girth conjecture for graphs with constant degree—there exist sparse graphs where every pivot-based one-hop ADO with any real stretch k requires space of size (e m one plustwo/(k+one)) <ref:2610.29624#pg1,girth conjecture for graphs with constant degree—there>.
Jane: That's significant because it matches the best known upper bounds for ADOs that have constant query time, up to polylogarithmic factors at every stretch where those bounds are already known. It connects a theoretical lower bound to what we think is achievable in practice.
Lalam: From my perspective, this paper shows that even with these clever pivot structures, when you're working with sparse graphs and constant degree assumptions, the space requirement still has that polynomial superlinear growth for any fixed stretch k.
Meng: If it requires (m one plustwo/(k+one)) space, then deploying this kind of oracle on large real-world networks where m is linear in n could quickly become prohibitively expensive if you need a high precision stretch <ref:2610.29624#pg1>.
Tom: It really highlights that the trade-off between query speed, stretch quality, and storage space isn't always smooth across all possible structures. This sets a very hard floor on the required space for this specific type of oracle under those conditions.
Conclusion: Jane: So, to wrap up what we just heard about "A Tight Space Lower Bound for Pivot-Based Distance Oracles," the authors are proving that for sparse graphs with constant degree, you can't get away with small space if you want a pivot-based ADO with a specific stretch k.
Tom: They establish that this lower bound, (e m one plustwo/(k+one)), is tight against the best known upper bounds for ADOs with constant query time at every stretch where those bounds are known <ref:2610.29624#pg1,query time at every stretch where>. It confirms that this trade-off is as good as it gets under the Erdős girth conjecture.
Lu: What I find particularly interesting is how they extend this idea to more hops, showing that for any constant number beta of hops, you get a similar bound involving two/(beta(k+one)) <ref:2610.29624#pg1>. That suggests the fundamental difficulty isn't just about one hop, but the structure of these pivot jumps.
Meng: From a deployment standpoint, it means if you're building a system that relies on these pivot-based structures to keep query time low, you have to budget for this superlinear space growth based on your desired stretch k. It’s not just an abstract math problem; it dictates hardware requirements.
Lalam: I'm fairly sure this result is robust because they even used explicit high-girth graphs from Double Agent to get unconditional versions of the lower bounds, which means we don't have to rely on that conjecture being true for the absolute best results.
More episodes
- 2505.16254-Human-AI Writing as Distributed Cognition: Reassessing Collaborative Writing Theories in the Age of LLMs
- 2506.10913-Choreographic Quick Changes: First-Class Location (Set) Polymorphism
- 2507.14812-A Black-Box Approach for Exogenous Replenishment in Online Resource Allocation
- 2507.15448-Frames over finite fields with respect to the Galois inner product and their connections to self-orthogonal and LCD codes
- 2508.21572-NewsReX: An Open-Source Multi-Framework for Neural News Recommendation
- 2509.17028-Impact of Packetization on Network Calculus Analysis
- 2510.17342-AoA Services in 5G Networks: A Framework for Real-World Implementation and Systematic Testing
- 2511.04088-Efficient and rate-optimal list-decoding in the presence of minimal feedback
- 2511.17264-Notes on Stack Machines and Quantum Stack Machines
- 2601.15318-On the closest balanced game