Connectivity in a New Bounded-Space Dynamic Model

arXiv:2611.08351 · cs.DS · Submitted 2026-11-05 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.

Tom: I'm Tom.

Jane: And I'm Jane, here with Lu, Meng and our in-house large language model, Lalam.

Tom: We're looking at the paper: "Connectivity in a New Bounded-Space Dynamic Model".

Jane: Here's the gist of the paper. The paper introduces a new model for dynamic algorithms where an algorithm has read-only access to a dynamically changing input and random access to its own bounded workspace for computation.

Tom: This model is a dynamic analogue of the time–space tradeoffs studied in complexity theory, where the input is stored separately and space is measured only by the algorithm's writable memory usage.

Jane: The study focuses on lower and upper bounds for dynamic undirected s-t connectivity: after every edge update to an n-vertex graph, an algorithm with S words of workspace must report whether two fixed vertices s and t are in the same connected component.

Tom: The algorithm has oracle access to the dynamically changing graph, either through adjacency list queries (giving the degree of a vertex or its j-th neighbor) or through adjacency matrix queries (asking if two vertices are adjacent).

Paper summary: Tom: So looking at this paper "Connectivity in a New Bounded-Space Dynamic Model," the main point is that they defined a new model for dynamic algorithms where space is only measured by the algorithm's own writable memory usage.

Jane: They established that for dynamic undirected s-t connectivity, you can get polynomial update time if your workspace S stays below n to the power of one minus a constant epsilon greater than zero.

Lu: The paper really hammers home that the lower bounds and upper bounds match up pretty closely for fully dynamic algorithms, even when you consider polylogarithmic factors.

Meng: This suggests that we have a very solid idea of the complexity here, not just some loose estimates.

Tom: And they showed specific time costs depending on whether you use an adjacency list or an adjacency matrix for querying the graph updates.

Jane: The implications are that for real-world systems dealing with constantly changing networks, if you need to maintain connectivity, you have to decide upfront how much memory S is going to dedicate and accept the corresponding update time cost.

Lu: They also provided deterministic algorithms for forests on both models, showing we can get specific bounds for those scenarios.

Meng: Ultimately, this means that when you design something dynamic that relies on connectivity, the budget isn't just about storing the graph; it’s about budgeting your writable memory very precisely.

Conclusion: Tom: So, we're wrapping up this look at "Connectivity in a New Bounded-Space Dynamic Model." Basically, they're looking at how fast you can keep track of whether two points are connected in a graph that keeps changing, but you only have a very small amount of memory for your own tracking.

Jane: That sounds like it could be super practical for things like monitoring network connections or tracking paths in real-time data streams. But the title itself is a bit technical, isn't it? "Connectivity in a New Bounded-Space Dynamic Model."

Lu: Yeah, yeah. The authors are talking about this new way of measuring space. They treat the graph as something you can look at whenever you want, but your own memory usage—your working space—is strictly limited to something much smaller than the whole graph itself.

Meng: From a deployment standpoint, that bounded workspace is key. It means we aren't just storing the massive input data; we're only managing the small state information needed to answer those connectivity questions quickly. That sounds like it could help us design algorithms for huge graphs where keeping everything in RAM is impossible.

Tom: Exactly, Meng. And what they find is that you can maintain this connection status in polynomial time per update, provided your memory limit isn't too big relative to the graph size n. It sets a clear boundary on the trade-off between update speed and the amount of workspace you use.

Jane: So, if I’m just listening, does that mean we can design a system where we know exactly how much memory we need before we start building it? That feels like a solid engineering concept.

Lu: It is. They proved that for certain graph structures and with certain query methods—like using adjacency lists or an adjacency matrix—you can get those polynomial time guarantees if your space stays below n to the power of one minus some small constant.

Tom: And they actually showed that the lower bounds for these dynamic algorithms match up really well with their upper bounds, even for fully dynamic scenarios. That’s a strong statement about how close we are to finding the absolute best possible way to handle this problem.

Jane: It means the theoretical limits they set are quite realistic for what we can actually build right now. It moves this from just an abstract complexity theory problem into something that has hard engineering constraints.

Meng: From my side, I'm interested in those specific time costs they mention for adjacency lists versus the matrix model. That’s where the practical performance differences really show up when you start running things at scale.

Lu: Yeah, and they did even find deterministic versions for these dynamic problems on graphs that are always forests, which is interesting because it shows you can sometimes avoid randomness altogether for specific structures.

Tom: So, to sum up: this paper gives us a clear map of the trade-off between how fast we can update a changing graph and how much memory our algorithm itself needs to keep track of things.

Jane: It's about setting measurable limits on dynamic connectivity algorithms so that engineers know exactly what performance they are aiming for when designing systems that constantly evolve.

Lu: And this opens up more avenues for thinking about how we represent complex data structures efficiently in a constantly shifting environment.

Bardiya Aryanfard, Monika Henzinger, John Kuszmaul, Jakob Nogler, Virginia Vassilevska Williams

Institute of Science and Technology Austria · Massachusetts Institute of Technology

cs.DS

Submitted: 2026-11-05

Updated: 2026-11-05

Comments: Submitted to STOC; shortened abstract to fit arxiv requirements

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Importance score: 99/100

The gist: The paper introduces a new model for dynamic algorithms where an algorithm has read-only access to a dynamically changing input and random access to its own bounded workspace for computation.

Key concepts

Dynamic Input Model
The input graph changes over time (edges are added or removed) while the algorithm only has read-only access to it. The algorithm's memory usage is measured separately, focusing on its writable workspace rather than the entire graph storage.
Workspace Space ($S$ words)
This measures the auxiliary memory an algorithm uses for computation, not the size of the input graph itself. A 'word' is a unit of storage containing $\Theta(\log n)$ bits. The constraint $S leq n^{1-\epsilon}$ dictates that if memory is too small compared to $n$, updates must take significant time.
Time-Space Tradeoff
The core finding shows that for dynamic connectivity, you cannot achieve very fast updates (polynomial time) if the memory constraint ($S$) is tight. Specifically, polynomial update time is required when $S$ is sublinear in $n$, linking the amount of memory available directly to the required computational effort per graph change.

Terminology

Summary

The paper introduces a new model for dynamic algorithms where an algorithm has read-only access to a dynamically changing input and random access to its own bounded workspace for computation. p. 0 This model is a dynamic analogue of the time–space tradeoffs studied in complexity theory, where the input is stored separately and space is measured only by the algorithm's writable memory usage. The study focuses on lower and upper bounds for dynamic undirected s-t connectivity: after every edge update to an n-vertex graph, an algorithm with S words of workspace must report whether two fixed vertices s and t are in the same connected component. p. 0 The algorithm has oracle access to the dynamically changing graph, either through adjacency list queries (giving the degree of a vertex or its j-th neighbor) or through adjacency matrix queries (asking if two vertices are adjacent). p. 0 The algorithms considered are randomized. p. 0

The model measures the auxiliary space of the algorithm and the cost of maintaining its answer, not the total storage used by the graph's owner. A word contains theta(n) bits. p. 3 The input is a simple undirected graph on [n], initially with no edges, along with two fixed terminals s, t in [n]. p. 3 Each update is announced before it takes effect; while processing an insertion or deletion, the algorithm can inspect the graph as it was before the update and must report whether s and t are connected after the update. p. 3 The central tension explored is how much time per update is needed to maintain s-t connectivity in a changing graph with S much less than n words of writable memory, given read access to the current graph, depending on the interface through which the graph can be inspected. p. 2

The main findings establish a time–space tradeoff: polynomial update time is necessary whenever S at most n 1-epsilon for a constant epsilon > 0, even for incremental algorithms with amortized guarantees. p. 0 Lower bounds for amortized and fully dynamic algorithms match the upper bounds up to polylogarithmic factors. p. 7 For instance, Theorem 4 (Fully dynamic amortized lower bound) shows that there exist constants eta, c > 0 such that for any randomized algorithm A using at most B bits of memory and at most T adjacency probes per update (amortized) for Dynamic s-t Connectivity in the fully dynamic setting, with B at most eta n and BT at most cn squared, there exists an input sequence sigma of length theta(n) such that the algorithm answers all queries correctly with probability less than 2/3 and the graph is a forest throughout the entire stream. p. 6

Specific lower bounds are provided for different models:

  • With adjacency lists, worst-case time theta(e n squared /S 2) per insertion is necessary and sufficient for incremental algorithms.

  • With an adjacency matrix, worst-case time omega(e n squared /S) per insertion is necessary for incremental algorithms, and it is sufficient for S at least sqrt n.

Amortization yields better upper bounds: With adjacency lists, incremental algorithms achieve amortized time O(n/S) per insertion. p. 0 With an adjacency matrix, the amortized time is O(n 2/S) for every S. p. 0 Lower bounds confirm these results, showing that every incremental algorithm needs amortized time omega(e n/S) with adjacency lists and omega(e n squared /S) with an adjacency matrix. p. 0 Strong unconditional lower bounds are also obtained for fully dynamic algorithms even when the graph is always a forest: Amortized time omega(e n/S) per update is necessary with adjacency lists and omega(e n squared /S) is necessary with an adjacency matrix. p. 0

The paper details reductions from the Index problem to establish lower bounds for incremental and fully dynamic algorithms (Theorem 5. p. 72 shows a lower bound on message size). p. 6 Constructions are provided to show that connectivity depends on specific bits or hidden random bits, used to establish worst-case lower bounds in the matrix model (Theorem 2). p. 5 The final results demonstrate that the amortized upper bounds for incremental connectivity match the amortized lower bounds for fully dynamic connectivity, up to polylogarithmic factors. p. 7 Deterministic algorithms are also provided for Dynamic s-t Connectivity on forests (Theorem 5), achieving O(S) space and O(n 2/S) time in the matrix model, or O((n/S)(delta + S)) in the list model if the maximum degree delta at least 1. p. 6

Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.

Improvements for AI systems

  1. Robust dynamic s-t connectivity maintenance for read-only inputs: The model allows an algorithm to maintain s-t connectivity in a changing graph with limited writable memory by only using a single bit of private memory, enabling monitoring systems to track connectivity after every update.

  2. Efficient incremental algorithms for dynamic updates: Algorithms can achieve amortized time Oe(n/S) per insertion in the list model and Oe(n 2/S) amortized time in the matrix model, providing a polynomial trade-off between update speed and workspace size S.

  3. Tight worst-case lower bounds for incremental connectivity: The paper establishes necessary worst-case times for incremental algorithms, showing that with adjacency lists, every incremental algorithm needs amortized time Omega(e pn/S), and with adjacency matrices, Omega(e n2/S) is necessary for S greater than the square root of n.

  4. Guiding memory constraints for dynamic connectivity: The lower bounds demonstrate that polynomial update time is necessary whenever S less than n(1-epsilon) for a constant epsilon greater than zero, even when only a single pair of vertices must be maintained.

  5. Amortized and fully dynamic lower bounds: The model establishes strong unconditional lower bounds for fully dynamic algorithms, showing that every incremental algorithm needs amortized time Omega(e pn/S) with adjacency lists and Omega(e n2/S) with adjacency matrices even when the graph is always a forest.

  6. Optimized memory usage via random walks: The upper bound analysis shows that algorithms can use space Oe(S + min(n, i)/S) for early insertions in the list model by employing simple random walks instead of full breadth-first searches, leading to faster initial updates.

  7. Complexity trade-off between query type: The model allows comparing different oracle interfaces; trading pairwise edge tests (adjacency matrix) for neighbor enumeration (adjacency list) changes the private memory needed for efficient dynamic algorithms in this setting.

  8. Formal reduction from Index problem: A formal reduction from the Public Coin Index problem to s-t connectivity shows that an incremental algorithm requires Omega(n 2/B 2) worst-case time per update in the matrix model when working memory is bounded by B bits, providing a hard lower bound for dynamic algorithms.

  9. Communication protocol design: The paper details a communication protocol between an owner and a monitor where the monitor's message to the owner can be compacted to at most B + 2 + 2B log2(ec/2) bits, significantly reducing communication overhead compared to sending all successful probe information explicitly.

Sources

Related papers