Unconditional Boolean Dynamic Lower Bounds from Disjointness

arXiv:2610.10904 · cs.DS, cs.CC · Submitted 2026-10-07 · 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: "Unconditional Boolean Dynamic Lower Bounds from Disjointness".

Jane: Here's the gist of the paper. We prove an unconditional lower bound of omega(log n/ log log n)2 on the maximum update time and query time for P˘atra¸scu’s multiphase problem with Disjointness, which matches the strongest known lower bound for any dynamic problem The Main Result The paper establishes an unconditional omega(log n/ log log n)2 lower bound on the maximum of the update time and query time for P˘atra¸scu’s multiphase problem with Disjointness in its insert-only form.

Tom: This bound is derived by reducing the problem to dynamic directed reachability <ref:2610.10904#pg31>, and it surpasses the bound of Larsen and Yu by a factor of √log n <ref:2610.10904#pg3>.

Jane: The result holds for many other incremental graph problems, including s-t reachability, strong connectivity, and triangle detection <ref:2610.10904#pg3>.

Tom: The Reduction Framework The proof relies on P˘atra¸scu’s reductions from the multiphase problem to dynamic graph problems <ref:2610.10904#pg30> and other related problems <ref:2610.10904#pg29>.

Paper summary: Tom: So we're looking at this paper today titled Unconditional Boolean Dynamic Lower Bounds from Disjointness. Essentially, they're proving an unconditional lower bound on how fast you can update and query for Patrascu’s multiphase problem with Disjointness in its insert-only form, and they claim it's about the log n over log log n squared scale.

Jane: That sounds like a really tough result to prove, Tom. What does that mean for us listening right now? Are we talking about something that forces us to rethink how we build dynamic data structures?

Lu: It means they took this multiphase problem and reduced it down to dynamic directed reachability in n-node directed acyclic graphs under edge insertions, and they showed this same bound holds there, which is an improvement over the log three fifth powers of n that Larsen and Yu had found before <ref:2610.10904#pg3>.

Meng: But what about the practical side? If we're deploying models in production, does this mean our update or query times will always be at least this slow, regardless of how clever our algorithm is?

Lalam: The paper establishes that this lower bound matches the strongest known lower bound for any dynamic problem <ref:2610.10904#pg3>.

Tom: Right, so it's not just a theoretical curiosity; it sets a new benchmark for what's possible in dynamic problems, which is pretty significant since we often rely on conditional lower bounds that can vanish with new conjectures.

Jane: That sounds like the core message—moving from conditional hardness to unconditional hardness. What kind of problems are covered by this result beyond the original Disjointness setup?

Lu: They show this bound holds for a lot of other dynamic problems, including incremental s-t reachability, strong connectivity and cycle detection in directed graphs, and undirected shortest paths or subgraph connectivity in undirected graphs <ref:2610.10904#pg3>.

Meng: So this isn't just about one specific problem; it applies to a whole class of dynamic graph problems. Does that mean we need to be extremely careful when choosing our data structure for things like network monitoring?

Lalam: It also extends this result to other problems like dynamic set disjointness and range mode, showing that the total time for those problems is at least log n over log n over tu w squared <ref:2610.10904#pg29>.

Tom: That's interesting because it shows the difficulty isn't isolated to one structure; it seems inherent in dynamic graph problems themselves under the cell-probe model, which is a very strong model for realistic architectures with word sizes of log n bits <ref:2610.10904#pg2>.

Jane: It’s important that this holds even when we consider the constraint that the word size is logarithmic in n, because that’s what we actually have on many real hardware systems. What about the methodology they used to get this result?

Lu: The proof uses a two-layered framework combining Fredman and Saks’s Chronogram method with a two point five round communication game developed by Ko FOCS two thousand twenty-six <ref:2610.10904#pg1>. The key technical move here was adapting that communication game, which usually deals with Inner Product, to work for the original Disjointness problem <ref:2610.10904#pg1>.

Meng: I'm curious about that adaptation. What exactly did they change in the communication game setup to make it work for Disjointness instead of Inner Product?

Lalam: The paper points out that the protocol’s verification step allows them to replace a discrepancy property with a one-sided corruption bound, which is what makes the proof work where previous attempts failed <ref:2610.10904#pg9>.

Tom: So, they found a way to get around a limitation in the game structure by changing how we check the protocol's correctness. That feels like a crucial piece of insight for applying this framework to other things later on.

Jane: What does that imply about the limits of this Chronogram method? Does it suggest that for Boolean problems, this new framework might be the limit we can reach?

Lu: The paper suggests that because they reduced Disjointness to reachability, and reachability captures natural dynamic graph problems, this framework is likely the limit of what we can achieve with the Chronogram method for Boolean problems <ref:2610.10904#pg15>.

Meng: That sounds ambitious. If this framework is the limit, it means we might not be able to get much better than log n over log n over tu w squared for these types of problems on real hardware.

Tom: It suggests that for many dynamic graph problems, the query time tq is fundamentally bound by that term, regardless of how clever we try to design the structure.

Jane: So, to summarize what we've heard about this paper Unconditional Boolean Dynamic Lower Bounds from Disjointness: they proved a very strong lower bound on update and query times for Pátrascu’s problem with Disjointness in its insert-only form, and that this bound holds for a wide range of dynamic graph problems.

Lu: It's important to remember that this unconditional result is robust against future algorithmic discoveries because it relies on first principles rather than conditional arguments <ref:2610.10904#pg2>.

Meng: I just hope we can find a way to break this log n over log n over tu w squared barrier in practice, even if the theory says it's unreachable for now.

Lalam: The paper shows that this bound on max update and query time is the strongest unconditional lower bound known for any dynamic problem <ref:2610.10904#pg3>.

Conclusion: Tom: So what's the main gist of this paper, Jane? What are they actually proving here?

Jane: They are showing an unconditional lower bound on the maximum update time and query time for Patrascu’s multiphase problem with Disjointness in its insert-only version. It's about how slow you have to be.

Lu: The authors took that problem and reduced it down to dynamic directed reachability under edge insertions in directed acyclic graphs of depth two. That's the key reduction they use to establish this lower bound.

Meng: So what does this mean for us in terms of deployment? If we're building something dynamic, does this tell us we're stuck with super-logarithmic time, no matter how clever our algorithm is?

Lalam: It means that for many dynamic problems, you simply can't do better than a query time that scales with the logarithm of n over the logarithm of tu w squared. That’s the number they derived.

Tom: That sounds pretty fundamental. So, what are the actual authors we're talking about here?

Jane: The paper is by an unknown team, but they use some really heavy machinery from communication games and Chronogram methods to get this result for Disjointness specifically.

Lu: They adapted a two point five round communication game framework, which usually deals with Inner Product, to work for the Disjointness problem. Their main trick was changing the verification step to use a one-sided corruption bound instead of the discrepancy property.

Meng: A one-sided corruption bound sounds more practical than what they used before. What's the big implication here for anyone working on these kinds of systems?

Lalam: It sets a new benchmark. This lower bound matches the strongest known lower bound for any dynamic problem, which is a big deal because it’s unconditional, meaning it holds no matter what future algorithms we discover.

Tom: So basically, this paper proves that you need super-logarithmic time for many dynamic graph problems under the cell-probe model. Where does this lead next?

Jane: It suggests that for Boolean problems, this Chronogram framework might be the limit of what you can get with these types of proofs. It points toward needing new techniques if we want to push past this barrier.

Pennsylvania State University

cs.DS, cs.CC

Submitted: 2026-10-07

Updated: 2026-11-02

Comments: 48 pages, 3 figures. v2: main result stated for the multiphase problem; appendix extended to further dynamic problems; introduction revised. v3: changed title, revised introduction and exposition, clarified appendix reductions, and updated references

Code: https://github.com/anthropics/formal-math

License: http://creativecommons.org/licenses/by/4.0/

Importance score: 89/100

The gist: We prove an unconditional lower bound of omega(log n/ log log n)2 on the maximum update time and query time for P˘atra¸scu’s multiphase problem with Disjointness…

Key concepts

Multiphase Disjointness Problem
This is a hard computational problem where you have multiple sets of queries that must be checked for disjointness. The goal is to determine if the intersection between these query sets is empty, which requires complex, multi-step checking processes.
Dynamic Directed Reachability
The paper reduces the Disjointness problem to checking reachability in a directed acyclic graph (DAG) with depth 2. This means determining if there is a path of length exactly two between two nodes, which serves as the core mechanism for proving the lower bound.
Chronogram Method
This is a two-layered framework combining geometric splitting (Chronogram) with a communication game analysis. The outer layer splits insertions into epochs, and the inner layer uses information theory to show that any data structure must take significant time to answer queries.

Summary

We prove an unconditional lower bound of omega(log n/ log log n)2 on the maximum update time and query time for P˘atra¸scu’s multiphase problem with Disjointness, which matches the strongest known lower bound for any dynamic problem

The Main Result

The paper establishes an unconditional omega(log n/ log log n)2 lower bound on the maximum of the update time and query time for P˘atra¸scu’s multiphase problem with Disjointness in its insert-only form. This bound is derived by reducing the problem to dynamic directed reachability <ref:2610. p. 0

Where the paper says it

Ω((log n/ log log n) 2 ) Lower Bounds for Dynamic Graph Problems Young Kun Ko∗ Abstract We prove an Ω(log n/ log log n) 2 unconditional lower bound on the maximum of the update time and the query time for P˘atra¸scu’s multiphase problem [STOC 2010] with Disjointness, in its insert-only form. Through his reductions, we obtain the same lower bound for dynamic data structures supporting reachability queries in n-node directed acyclic graphs under edge insertions, improving the Ωe(log3/2 n) lower bound of Larsen and Yu [SICOMP 2025], and matching the strongest lower bound known for any dynamic problem.

10904#pg31>, and it surpasses the bound of Larsen and Yu by a factor of √log n <ref:2610. p. 1
Where the paper says it

Through his reductions, we obtain the same bound for dynamic directed reachability: every zero-error data structure with worst-case update time tu and expected query time tq has tq = Ω(log n/ log(tuw))2 , already for incremental reachability on depth-2 DAGs (Theorem 1. This surpasses the bound of Larsen and Yu by a factor of √ log n (Fig.

10904#pg3>. The result holds for many other incremental graph problems, including s-t reachability, strong connectivity, and triangle detection <ref:2610. p. 0
Where the paper says it

Through his reductions, we obtain the same lower bound for dynamic data structures supporting reachability queries in n-node directed acyclic graphs under edge insertions, improving the Ωe(log3/2 n) lower bound of Larsen and Yu [SICOMP 2025], and matching the strongest lower bound known for any dynamic problem. The same bound holds for many other dynamic problems: in directed graphs, for incremental s-t reachability, strong connectivity and cycle detection; in undirected graphs, for incremental shortest paths, subgraph connectivity and triangle detection; and for dynamic set disjointness, range mode, and Langerman’s, Pagh’s and Erickson’s problems.

10904#pg3>.

The Reduction Framework

The proof relies on P˘atra¸scu’s reductions from the multiphase problem to dynamic graph problems <ref:2610.10904#pg30> and other related problems <ref:2610. p. 3

Where the paper says it

As discussed in [Ko26], it is likely the limit of the Chronogram framework, so Boolean problems can now be brought up to the best bounds that the Chronogram framework can give. Inner Product, however, is not known to capture natural dynamic graph problems: P˘atra¸scu’s reductions to reachability and related problems start from Disjointness.

10904#pg29>. The reduction involves constructing a directed acyclic graph (DAG) of depth 2 where reachability queries determine whether the query sets are disjoint <ref:2610. p. 0
Where the paper says it

Ω((log n/ log log n) 2 ) Lower Bounds for Dynamic Graph Problems Young Kun Ko∗ Abstract We prove an Ω(log n/ log log n) 2 unconditional lower bound on the maximum of the update time and the query time for P˘atra¸scu’s multiphase problem [STOC 2010] with Disjointness, in its insert-only form. Through his reductions, we obtain the same lower bound for dynamic data structures supporting reachability queries in n-node directed acyclic graphs under edge insertions, improving the Ωe(log3/2 n) lower bound of Larsen and Yu [SICOMP 2025], and matching the strongest lower bound known for any dynamic problem.

10904#pg30>. Specifically, the distance between a fixed source and a target vertex is exactly 2 if and only if Sq ∩ X ≠ ∅ <ref:2610.10904#pg32>. This reduction allows the authors to transfer the lower bound from dynamic graph problems to the multiphase Disjointness problem <ref:2610. p. 0
Where the paper says it

Ω((log n/ log log n) 2 ) Lower Bounds for Dynamic Graph Problems Young Kun Ko∗ Abstract We prove an Ω(log n/ log log n) 2 unconditional lower bound on the maximum of the update time and the query time for P˘atra¸scu’s multiphase problem [STOC 2010] with Disjointness, in its insert-only form. Through his reductions, we obtain the same lower bound for dynamic data structures supporting reachability queries in n-node directed acyclic graphs under edge insertions, improving the Ωe(log3/2 n) lower bound of Larsen and Yu [SICOMP 2025], and matching the strongest lower bound known for any dynamic problem.

10904#pg29>.

The Chronogram Method

The core of the proof utilizes a two-layered framework combining Fredman and Saks’s Chronogram method with a 2.5-round communication game framework developed by Ko. p. 0

Where the paper says it

Ko [FOCS 2026] recently proved this bound for a variant of the multiphase problem with Inner Product in place of Disjointness, via a 2. 5-round multiphase communication game; we bring this framework to the original problem.

The outer layer uses the Chronogram method to split insertions into epochs whose sizes grow geometrically <ref:2610. p. 5
Where the paper says it

Section 3 gives the details. 1 The outer layer: the Chronogram method At a high level, the Chronogram method [FS89] divides the insertions into ℓ epochs whose sizes grow geometrically going back in time.

10904#pg14> and shows that a query must probe a certain number of cells in a constant fraction of these epochs <ref:2610. p. 5
Where the paper says it

and Saks [FS89]: we split the insertions into Θ(log n/ log(tuw)) epochs, and show that a query must probe Ω(log n/ log(tuw)) cells written in each of a constant fraction of them. The inner layer proves this bound for a single epoch, following [Ko26]: if a query probes fewer cells of the epoch, we turn the data structure into a too-good-to-be-true protocol for a 2.

10904#pg15>. This leads to the bound tq = omega(log n/ log(tuw))2. p. 1
Where the paper says it

In this work, we prove an unconditional Ω(log n/ log log n) 2 lower bound for the multiphase problem of P˘atra¸scu [Pat10] with Disjointness, in its insert-only form (Theorem 1. Through his reductions, we obtain the same bound for dynamic directed reachability: every zero-error data structure with worst-case update time tu and expected query time tq has tq = Ω(log n/ log(tuw))2 , already for incremental reachability on depth-2 DAGs (Theorem 1.

The Communication Game Analysis

The inner layer analyzes a restricted version of P˘atra¸scu’s multiphase communication game, referred to as Protocol 1, using information-theoretic arguments. The simulation protocol shows that a too-good-to-be-true data structure yields a protocol where Bob outputs “disjoint” with probability n−o(1) <ref:2610. p. 7

Where the paper says it

Simulation (Section 3. A too-good-to-be-true data structure yields a protocol for the game of Protocol 1 in which Bob outputs “disjoint” with probability n −o(1), and every answer he outputs is correct.

10904#pg16>. The analysis then proceeds by showing that if the query time tq were smaller, this protocol would be too good to exist, leading to a contradiction. p. 6
Where the paper says it

Yet Bob learns, with probability n −o(1), that SQ and X are disjoint. This is what makes the protocol too good to exist.

The Contradiction via Rectangles

The final step involves showing that the distribution of (S(i)Q, X(i)) given the accepted answers forms a monochromatic near-rectangle <ref:2610.10904#pg22>. By replacing this near-rectangle with the product of its marginals, it becomes an (εsi/2)-rectangle <ref:2610. p. 7

Where the paper says it

A nearly monochromatic rectangle (Section 3. By Pinsker’s inequality, replacing this distribution by the product of its two marginals moves little mass.

10904#pg22>. The corruption bound then shows that no such rectangle exists because two independent sparse sets with high min-entropy cannot intersect with noticeable probability. p. 7
Where the paper says it

We can then condition on the answer “disjoint”, and only need that every product distribution with nearly full min-entropy puts noticeable mass on intersecting pairs towards the contradiction. This one-sided corruption bound does hold for Disjointness: it is precisely the rectangle bound of Babai, Frankl and Simon [BFS86], which we adapt to our sparser sets in Section 4.

This contradiction establishes the lower bound tq ≥ omega(log n/ log(tuw))2 <ref:2610. p. 5
Where the paper says it

2 The inner layer: a 2. 5-round multiphase communication game Suppose, for contradiction, that tq = o (log n/ log(tuw))2 , and fix an epoch i in which a random query probes only k = O(tq/ℓ) cells of Ci in expectation.

10904#pg13>.

Other Dynamic Problems

The paper extends the result to other dynamic problems by showing that their reductions also yield similar bounds. For instance, for dynamic set disjointness and dynamic range mode, the bound is max(tu, tq) ≥ omega(log N/ log log N)2 <ref:2610. p. 0

Where the paper says it

Through his reductions, we obtain the same lower bound for dynamic data structures supporting reachability queries in n-node directed acyclic graphs under edge insertions, improving the Ωe(log3/2 n) lower bound of Larsen and Yu [SICOMP 2025], and matching the strongest lower bound known for any dynamic problem. The same bound holds for many other dynamic problems: in directed graphs, for incremental s-t reachability, strong connectivity and cycle detection; in undirected graphs, for incremental shortest paths, subgraph connectivity and triangle detection; and for dynamic set disjointness, range mode, and Langerman’s, Pagh’s and Erickson’s problems.

10904#pg29>. The reduction for these problems shows that the query cost is O(tu + tq) or even O(tq) for queries without an update <ref:2610. p. 2
Where the paper says it

For problems whose queries return a single bit, such as reachability, there was no technique for proving even an ω(log n) lower bound until the breakthrough of Larsen, Weinstein and Yu [LWY20], who proved Ωe(log3/2 n). Building on their technique, Larsen and Yu [LY25] finally obtained the first super-logarithmic lower bound for a natural graph problem: for n-vertex DAGs under edge insertions, with worst-case update time tu, expected query time tq and word size w = Ω(log n), they show tq = Ωlog3/2 n/ log2 (tuw) [LY25, Theorem 1], so, for w = Θ(log n), max(tu, tq) = Ωe(log3/2 n).

10904#pg33>.

The Lower Bound Derivation

The lower bound derivation hinges on counting facts about the hard distribution, such as Claim 3.2, which states that each block Bi is disjoint with probability at least 1/4 <ref:2610. p. 5

Where the paper says it

By the birthday paradox, two random sets of size si in a universe of size ℓs2 i meet with probability about 1/ℓ. So the answer is “disjoint” with constant probability, and each block can change it.

10904#pg14>. The analysis of the min-entropy and mutual information under conditioning on the accepted answer leads to a contradiction when assuming tq is smaller than the derived bound. p. 7
Where the paper says it

We can then condition on the answer “disjoint”, and only need that every product distribution with nearly full min-entropy puts noticeable mass on intersecting pairs towards the contradiction. This one-sided corruption bound does hold for Disjointness: it is precisely the rectangle bound of Babai, Frankl and Simon [BFS86], which we adapt to our sparser sets in Section 4.

This confirms that tq ≥ n−o(1).

The Corruption Bound Details

The proof of the corruption bound for sparse sets adapts Babai, Frankl and Simon’s argument to sparser regimes where N is a multiple of s squared <ref:2610.10904#pg25>. The key insight is that a long chain of rows and grouping pieces into groups allows the application of counting facts to show that any large rectangle must have significant intersection mass <ref:2610.10904#pg26>. This confirms the lower bound tq ≥ n−1/6 for every epoch i in I. p. 1

Where the paper says it

This distinction recently became concrete: two of the three central conjectures of fine-grained complexity, the 3SUM and APSP conjectures, were refuted using AI [AW26, KL26], with a truly subquadratic algorithm for 3SUM and a truly subcubic one for APSP, and the result has been formalized in Lean. 1 Every lower bound conditioned on them, including P˘atra¸scu’s original evidence for the multiphase problem that this paper builds on, lost its support at once.

The Final Contradiction

By combining the results from the simulation theorem, monochromatic near-rectangle analysis, and the corruption bound, the authors conclude that no such structure can exist under the assumption of a smaller query time <ref:2610.10904#pg27>. The resulting contradiction proves Theorem 3. p. 7

Where the paper says it

1 from Theorem 3. Section 3 defines the hard distribution, proves the simulation theorem (Step 1) and the communication lower bound (Steps 2–4), and completes the proof of Theorem 3.

1 <ref:2610. p. 0
Where the paper says it

∗Department of Computer Science and Engineering, Pennsylvania State University, University Park, PA, USA. edu 1 arXiv:2610.

10904#pg13>. The final conclusion is that tq ≥ n−o(1). p. 6
Where the paper says it

• Merlin’s message U is the list of all cells written in epochs i, . , 1, with their final contents.

The General Bound

Theorem A.1 summarizes the lower bounds for various dynamic graph problems, stating that for all listed problems, max(tu, tq) ≥ omega(log N/ log log N)2 <ref:2610. p. 0

Where the paper says it

Ω((log n/ log log n) 2 ) Lower Bounds for Dynamic Graph Problems Young Kun Ko∗ Abstract We prove an Ω(log n/ log log n) 2 unconditional lower bound on the maximum of the update time and the query time for P˘atra¸scu’s multiphase problem [STOC 2010] with Disjointness, in its insert-only form. Through his reductions, we obtain the same lower bound for dynamic data structures supporting reachability queries in n-node directed acyclic graphs under edge insertions, improving the Ωe(log3/2 n) lower bound of Larsen and Yu [SICOMP 2025], and matching the strongest lower bound known for any dynamic problem.

10904#pg31>. This confirms the general applicability of the derived bound to a wide range of dynamic data structures <ref:2610. p. 0
Where the paper says it

Through his reductions, we obtain the same lower bound for dynamic data structures supporting reachability queries in n-node directed acyclic graphs under edge insertions, improving the Ωe(log3/2 n) lower bound of Larsen and Yu [SICOMP 2025], and matching the strongest lower bound known for any dynamic problem. The same bound holds for many other dynamic problems: in directed graphs, for incremental s-t reachability, strong connectivity and cycle detection; in undirected graphs, for incremental shortest paths, subgraph connectivity and triangle detection; and for dynamic set disjointness, range mode, and Langerman’s, Pagh’s and Erickson’s problems.

10904#pg31>. The bound holds even when tu ≥ log2 N, in which case log(tuw) = O(log log N) <ref:2610. p. 2
Where the paper says it

For problems whose queries return a single bit, such as reachability, there was no technique for proving even an ω(log n) lower bound until the breakthrough of Larsen, Weinstein and Yu [LWY20], who proved Ωe(log3/2 n). Building on their technique, Larsen and Yu [LY25] finally obtained the first super-logarithmic lower bound for a natural graph problem: for n-vertex DAGs under edge insertions, with worst-case update time tu, expected query time tq and word size w = Ω(log n), they show tq = Ωlog3/2 n/ log2 (tuw) [LY25, Theorem 1], so, for w = Θ(log n), max(tu, tq) = Ωe(log3/2 n).

10904#pg29>.

The Role of AI Methodology

The proof of the technical Theorem 4.1 was developed with the assistance of an AI model (Claude Opus 5. p. 2

Where the paper says it

Conditional lower bounds. To argue that these algorithms are close to optimal, a series of conditional lower bounds has been developed since 2010.

5), which helped adapt the corruption argument from Babai, Frankl and Simon [BFS86] <ref:2610. p. 7
Where the paper says it

This one-sided corruption bound does hold for Disjointness: it is precisely the rectangle bound of Babai, Frankl and Simon [BFS86], which we adapt to our sparser sets in Section 4. More generally, the argument uses Disjointness only through the answers of accepted runs and the fact that intersection is an OR over the blocks, so any OR over the blocks of functions with an analogous one-sided corruption bound would give the same lower bound for its multiphase problem.

10904#pg24>. The authors verified both parts in full <ref:2610. p. 0
Where the paper says it

∗Department of Computer Science and Engineering, Pennsylvania State University, University Park, PA, USA. edu 1 arXiv:2610.

10904#pg24>. This highlights a modern approach to proving complex combinatorial lower bounds using computational assistance <ref:2610. p. 1
Where the paper says it

Conditional lower bounds have been remarkably successful at charting which problems are as hard as which, but only unconditional lower bounds truly tell us that a problem is hard. This distinction recently became concrete: two of the three central conjectures of fine-grained complexity, the 3SUM and APSP conjectures, were refuted using AI [AW26, KL26], with a truly subquadratic algorithm for 3SUM and a truly subcubic one for APSP, and the result has been formalized in Lean.

10904#pg24>.

The Reductions Summary

Appendix A details the reductions from the multiphase problem to dynamic graph problems and other problems like dynamic range mode. These reductions are simple variants of P˘atra¸scu’s graph reduction <ref:2610. p. 1

Where the paper says it

1), and matches the strongest lower bound known for any dynamic problem [Lar12, Ko26], which, as argued in [Ko26], is likely the limit of the Chronogram framework. Through P˘atra¸scu’s reductions and simple variants of them, the same Ω (log n/ log log n) 2 bound holds for many other incremental graph problems: for s-t reachability, 1See the 3sum-apsp folder of https://github.

10904#pg30>. The analysis shows that every insertion into X is simulated by O(1) updates in these settings, which validates the insert-only setting. p. 4
Where the paper says it

2 (Main technical theorem, informal). Every zero-error cell-probe data structure for insert-only multiphase Disjointness with m = n query sets, word size w = Θ(log n), worst-case update time tu per insertion and expected query time tq has tq = Ω(log n/ log(tuw))2 .

The Lower Bound for Other Problems

Theorem A.2 provides lower bounds for dynamic set disjointness, Langerman’s problem, Pagh’s problem, Erickson’s problem or dynamic range mode <ref:2610. p. 0

Where the paper says it

Through his reductions, we obtain the same lower bound for dynamic data structures supporting reachability queries in n-node directed acyclic graphs under edge insertions, improving the Ωe(log3/2 n) lower bound of Larsen and Yu [SICOMP 2025], and matching the strongest lower bound known for any dynamic problem. The same bound holds for many other dynamic problems: in directed graphs, for incremental s-t reachability, strong connectivity and cycle detection; in undirected graphs, for incremental shortest paths, subgraph connectivity and triangle detection; and for dynamic set disjointness, range mode, and Langerman’s, Pagh’s and Erickson’s problems.

10904#pg31>. These problems are shown to be solvable with total time tu + tq ≥ omega(log N/ log(tuw))2 <ref:2610. p. 2
Where the paper says it

For problems whose queries return a single bit, such as reachability, there was no technique for proving even an ω(log n) lower bound until the breakthrough of Larsen, Weinstein and Yu [LWY20], who proved Ωe(log3/2 n). Building on their technique, Larsen and Yu [LY25] finally obtained the first super-logarithmic lower bound for a natural graph problem: for n-vertex DAGs under edge insertions, with worst-case update time tu, expected query time tq and word size w = Ω(log n), they show tq = Ωlog3/2 n/ log2 (tuw) [LY25, Theorem 1], so, for w = Θ(log n), max(tu, tq) = Ωe(log3/2 n).

10904#pg29>. For set disjointness, Pagh’s problem and dynamic range mode, the first bound holds with tq in place of tu + tq <ref:2610. p. 0
Where the paper says it

The same bound holds for many other dynamic problems: in directed graphs, for incremental s-t reachability, strong connectivity and cycle detection; in undirected graphs, for incremental shortest paths, subgraph connectivity and triangle detection; and for dynamic set disjointness, range mode, and Langerman’s, Pagh’s and Erickson’s problems. Ko [FOCS 2026] recently proved this bound for a variant of the multiphase problem with Inner Product in place of Disjointness, via a 2.

10904#pg29>. The bound on max(tu, tq) is also established for these problems <ref:2610. p. 2
Where the paper says it

For problems whose queries return a single bit, such as reachability, there was no technique for proving even an ω(log n) lower bound until the breakthrough of Larsen, Weinstein and Yu [LWY20], who proved Ωe(log3/2 n). Building on their technique, Larsen and Yu [LY25] finally obtained the first super-logarithmic lower bound for a natural graph problem: for n-vertex DAGs under edge insertions, with worst-case update time tu, expected query time tq and word size w = Ω(log n), they show tq = Ωlog3/2 n/ log2 (tuw) [LY25, Theorem 1], so, for w = Θ(log n), max(tu, tq) = Ωe(log3/2 n).

10904#pg31>.

The Final Conclusion on Complexity

The paper demonstrates that dynamic graph problems require super-logarithmic time for queries or updates under the cell-probe model <ref:2610.10904#pg29>. The derived bound tq = omega(log n/ log(tuw))2 is the strongest unconditional lower bound known for any dynamic problem. p. 0

Where the paper says it

Ω((log n/ log log n) 2 ) Lower Bounds for Dynamic Graph Problems Young Kun Ko∗ Abstract We prove an Ω(log n/ log log n) 2 unconditional lower bound on the maximum of the update time and the query time for P˘atra¸scu’s multiphase problem [STOC 2010] with Disjointness, in its insert-only form. Through his reductions, we obtain the same lower bound for dynamic data structures supporting reachability queries in n-node directed acyclic graphs under edge insertions, improving the Ωe(log3/2 n) lower bound of Larsen and Yu [SICOMP 2025], and matching the strongest lower bound known for any dynamic problem.

p. 0
Where the paper says it

Ω((log n/ log log n) 2 ) Lower Bounds for Dynamic Graph Problems Young Kun Ko∗ Abstract We prove an Ω(log n/ log log n) 2 unconditional lower bound on the maximum of the update time and the query time for P˘atra¸scu’s multiphase problem [STOC 2010] with Disjointness, in its insert-only form. Through his reductions, we obtain the same lower bound for dynamic data structures supporting reachability queries in n-node directed acyclic graphs under edge insertions, improving the Ωe(log3/2 n) lower bound of Larsen and Yu [SICOMP 2025], and matching the strongest lower bound known for any dynamic problem.

p. 0
Where the paper says it

Ω((log n/ log log n) 2 ) Lower Bounds for Dynamic Graph Problems Young Kun Ko∗ Abstract We prove an Ω(log n/ log log n) 2 unconditional lower bound on the maximum of the update time and the query time for P˘atra¸scu’s multiphase problem [STOC 2010] with Disjointness, in its insert-only form. Through his reductions, we obtain the same lower bound for dynamic data structures supporting reachability queries in n-node directed acyclic graphs under edge insertions, improving the Ωe(log3/2 n) lower bound of Larsen and Yu [SICOMP 2025], and matching the strongest lower bound known for any dynamic problem.

p. 0
Where the paper says it

Ω((log n/ log log n) 2 ) Lower Bounds for Dynamic Graph Problems Young Kun Ko∗ Abstract We prove an Ω(log n/ log log n) 2 unconditional lower bound on the maximum of the update time and the query time for P˘atra¸scu’s multiphase problem [STOC 2010] with Disjointness, in its insert-only form. Through his reductions, we obtain the same lower bound for dynamic data structures supporting reachability queries in n-node directed acyclic graphs under edge insertions, improving the Ωe(log3/2 n) lower bound of Larsen and Yu [SICOMP 2025], and matching the strongest lower bound known for any dynamic problem.

This result underscores the necessity of super-logarithmic time complexity for these problems in realistic architectures <ref:2610. p. 2
Where the paper says it

For problems whose queries return a single bit, such as reachability, there was no technique for proving even an ω(log n) lower bound until the breakthrough of Larsen, Weinstein and Yu [LWY20], who proved Ωe(log3/2 n). Building on their technique, Larsen and Yu [LY25] finally obtained the first super-logarithmic lower bound for a natural graph problem: for n-vertex DAGs under edge insertions, with worst-case update time tu, expected query time tq and word size w = Ω(log n), they show tq = Ωlog3/2 n/ log2 (tuw) [LY25, Theorem 1], so, for w = Θ(log n), max(tu, tq) = Ωe(log3/2 n).

10904#pg2>. The paper also notes that conditional lower bounds are unreliable due to recent breakthroughs in related conjectures <ref:2610. p. 1
Where the paper says it

1 Every lower bound conditioned on them, including P˘atra¸scu’s original evidence for the multiphase problem that this paper builds on, lost its support at once. As this turn of events shows, conditional lower bounds carry an inherent logical danger: they are only as sound as the conjectures they rest on.

10904#pg3>.

The Significance of Unconditional Bounds

Unconditional lower bounds are presented as eternal statements, contrasting them with conditional lower bounds that can vanish overnight <ref:2610.10904#pg3>. This makes the unconditional result robust against future algorithmic discoveries and provides a stronger guarantee of hardness. The paper emphasizes that striving for unconditional lower bounds is crucial for establishing true hardness <ref:2610. p. 3

Where the paper says it

Despite this progress, it has long been conjectured that the true lower bound is much higher. Besides the conditional lower bounds above, P˘atra¸scu [Pat10] conjectured that the multiphase problem requires polynomial time, and identified a three-party communication game, now known as the multiphase communication game, whose hardness would imply this even in the cell-probe model, i.

10904#pg3>.

The Chronogram Framework Evolution

The paper traces the evolution of lower bounds in the cell-probe model from Fredman and Saks [FS89] to Larsen and Yu [LY25]. Each improvement required a conceptual shift in proof technique. p. 2

Where the paper says it

1 summarizes this progress. Each of these improvements may look marginal, but each required a conceptual shift in proof technique.

The current bound is the result of replacing the one-way communication game with a 2. p. 3
Where the paper says it

Larsen, Weinstein and Yu [LWY20] extended it to Boolean queries, by reducing to a one-way communication game in which Bob only needs to guess the answer with a small advantage over random guessing, which they analyze via a peak-to-average lemma based on Chebyshev polynomials. Despite this progress, it has long been conjectured that the true lower bound is much higher.

5-round game that allows for verification <ref:2610. p. 0
Where the paper says it

5-round multiphase communication game; we bring this framework to the original problem. Our main technical contribution is to show that verification in this game makes a one-sided corruption bound suffice in place of discrepancy, which Disjointness lacks.

10904#pg8>. This new framework matches the strongest known lower bound for weighted problems <ref:2610. p. 3
Where the paper says it

This bound matches the strongest lower bound known for any dynamic problem, which Larsen [Lar12] proved for a weighted problem whose queries return Θ(log n) bits. As discussed in [Ko26], it is likely the limit of the Chronogram framework, so Boolean problems can now be brought up to the best bounds that the Chronogram framework can give.

10904#pg15>.

The Limit of Current Techniques

The paper suggests that Boolean problems can now be brought up to the best bounds provided by the Chronogram framework, as demonstrated by Ko [Ko26] <ref:2610.10904#pg15>. The reduction from Disjointness to reachability is key because it allows this framework to capture natural dynamic graph problems <ref:2610. p. 3

Where the paper says it

As discussed in [Ko26], it is likely the limit of the Chronogram framework, so Boolean problems can now be brought up to the best bounds that the Chronogram framework can give. Inner Product, however, is not known to capture natural dynamic graph problems: P˘atra¸scu’s reductions to reachability and related problems start from Disjointness.

10904#pg15>. This suggests that the current technique is likely the limit of the Chronogram framework for Boolean problems <ref:2610. p. 3
Where the paper says it

This bound matches the strongest lower bound known for any dynamic problem, which Larsen [Lar12] proved for a weighted problem whose queries return Θ(log n) bits. As discussed in [Ko26], it is likely the limit of the Chronogram framework, so Boolean problems can now be brought up to the best bounds that the Chronogram framework can give.

10904#pg15>.

The Nature of Verification

The crucial technical contribution lies in showing that verification in the game makes a one-sided corruption bound sufficient instead of discrepancy, which Disjointness lacks <ref:2610.10904#pg9>. This one-sided property is what allows the proof to succeed where previous attempts failed. p. 7

Where the paper says it

As remarked in [Ko26], we do not expect the direct application of [Ko26] to work for Disjointness. Our key observation is that verification makes a much weaker, one-sided property enough.

The protocol is too good because Bob knows exactly when the simulation fails, allowing him to output FAIL instead of a guess <ref:2610. p. 7
Where the paper says it

As noted in [Ko26], the fact that the players know when the simulation fails is not used there. We use it: Bob outputs FAIL instead of a guess, so every answer he outputs is correct.

10904#pg16>.

The Final Bound Comparison

The paper compares the new bound with previous results. It surpasses Larsen and Yu's bound by a factor of √log n <ref:2610.10904#pg3>. It also matches the strongest lower bound known for any dynamic problem, which is likely the limit of the Chronogram framework <ref:2610. p. 1

Where the paper says it

This surpasses the bound of Larsen and Yu by a factor of √ log n (Fig. 1), and matches the strongest lower bound known for any dynamic problem [Lar12, Ko26], which, as argued in [Ko26], is likely the limit of the Chronogram framework.

10904#pg3>. This indicates that this result represents a significant step forward in establishing unconditional complexity limits <ref:2610. p. 1
Where the paper says it

Conditional lower bounds have been remarkably successful at charting which problems are as hard as which, but only unconditional lower bounds truly tell us that a problem is hard. This distinction recently became concrete: two of the three central conjectures of fine-grained complexity, the 3SUM and APSP conjectures, were refuted using AI [AW26, KL26], with a truly subquadratic algorithm for 3SUM and a truly subcubic one for APSP, and the result has been formalized in Lean.

10904#pg3>.

The Future Direction

The paper points toward future research by noting that P˘atra¸scu conjectured polynomial time for the multiphase problem, and lower bounds for its variants are known only in restricted settings <ref:2610.10904#pg14>. The authors suggest that further progress requires moving beyond the current framework to tackle the full complexity of P˘atra¸scu’s original communication game <ref:2610. p. 3

Where the paper says it

Despite this progress, it has long been conjectured that the true lower bound is much higher. Besides the conditional lower bounds above, P˘atra¸scu [Pat10] conjectured that the multiphase problem requires polynomial time, and identified a three-party communication game, now known as the multiphase communication game, whose hardness would imply this even in the cell-probe model, i.

10904#pg15>. This sets a clear direction for future research in this area <ref:2610. p. 0
Where the paper says it

∗Department of Computer Science and Engineering, Pennsylvania State University, University Park, PA, USA. edu 1 arXiv:2610.

10904#pg15>.

The Importance of Unconditional Bounds

Unconditional lower bounds are emphasized as being eternal compared to conditional ones that can disappear with new conjectures. This makes the unconditional result a statement of true hardness, regardless of future conjecture status <ref:2610.10904#pg3>. The paper stresses that this is why we must always strive for unconditional lower bounds <ref:2610. p. 1

Where the paper says it

2 Unconditional lower bounds are sometimes seen as quantitatively weak next to conditional ones, but this compares statements of different kinds: a conditional lower bound can disappear overnight, while an unconditional one, however modest, is eternal. This is why we must always strive for unconditional lower bounds.

p. 1
Where the paper says it

2 Unconditional lower bounds are sometimes seen as quantitatively weak next to conditional ones, but this compares statements of different kinds: a conditional lower bound can disappear overnight, while an unconditional one, however modest, is eternal. This is why we must always strive for unconditional lower bounds.

10904#pg2>.

The Cell-Probe Model Strength

The cell-probe model is considered very strong because it applies to every realistic architecture where memory consists of cells of w = Θ(log n) bits <ref:2610.10904#pg2>. This strength means that the results apply to every realistic architecture. p. 1

Where the paper says it

Unconditional lower bounds for data structures are proved in the cell-probe model [Yao81]. Memory consists of cells of w = Θ(log n) bits, a data structure is charged one unit for each cell it reads or writes, and computation is free, so a lower bound in this model applies to every realistic architecture.

Cell-probe lower bounds are among the hardest unconditional lower bounds to prove, facing natural-proofs barriers <ref:2610. p. 1
Where the paper says it

In the dynamic setting, the update time tu and the query time tq are the numbers of cells probed by an update and by a query, respectively. Because the model is so strong, cell-probe lower bounds are among the hardest unconditional lower bounds to prove: for static data structures, even slight improvements of the known bounds would imply new circuit lower bounds [Vio18, DGW19, KPI25], and strong ones face a natural-proofs barrier [KLMS26].

10904#pg7>.

The Bound on tq

The main conclusion is that for dynamic directed reachability, every zero-error data structure has a query time tq = omega(log n/ log(tuw))2. This implies that max(tu, tq) = omega(log n/ log log n)2 <ref:2610. p. 1

Where the paper says it

Because the model is so strong, cell-probe lower bounds are among the hardest unconditional lower bounds to prove: for static data structures, even slight improvements of the known bounds would imply new circuit lower bounds [Vio18, DGW19, KPI25], and strong ones face a natural-proofs barrier [KLMS26]. For dynamic directed reachability, the best unconditional lower bound, due to Larsen and Yu [LY25], is max(tu, tq) = Ω(log e 3/2 n).

10904#pg3>. This is the central quantitative finding of the paper <ref:2610. p. 1
Where the paper says it

This distinction recently became concrete: two of the three central conjectures of fine-grained complexity, the 3SUM and APSP conjectures, were refuted using AI [AW26, KL26], with a truly subquadratic algorithm for 3SUM and a truly subcubic one for APSP, and the result has been formalized in Lean. 1 Every lower bound conditioned on them, including P˘atra¸scu’s original evidence for the multiphase problem that this paper builds on, lost its support at once.

10904#pg15>.

The Comparison with Previous Bounds

The bound tq = omega(log n/ log(tuw))2 surpasses the bound of Larsen and Yu by a factor of √log n <ref:2610.10904#pg3>. It also matches the strongest lower bound known for any dynamic problem <ref:2610. p. 1

Where the paper says it

This surpasses the bound of Larsen and Yu by a factor of √ log n (Fig. 1), and matches the strongest lower bound known for any dynamic problem [Lar12, Ko26], which, as argued in [Ko26], is likely the limit of the Chronogram framework.

10904#pg3>. This result is significant because it establishes a new benchmark for complexity limits in this area. p. 1
Where the paper says it

Conditional lower bounds have been remarkably successful at charting which problems are as hard as which, but only unconditional lower bounds truly tell us that a problem is hard. This distinction recently became concrete: two of the three central conjectures of fine-grained complexity, the 3SUM and APSP conjectures, were refuted using AI [AW26, KL26], with a truly subquadratic algorithm for 3SUM and a truly subcubic one for APSP, and the result has been formalized in Lean.

The paper notes that this result is likely the limit of the Chronogram framework <ref:2610. p. 1
Where the paper says it

This surpasses the bound of Larsen and Yu by a factor of √ log n (Fig. 1), and matches the strongest lower bound known for any dynamic problem [Lar12, Ko26], which, as argued in [Ko26], is likely the limit of the Chronogram framework.

10904#pg15>.

The Role of Disjointness

The problem of Disjointness serves as the hard problem because P˘atra¸scu conjectured it requires polynomial time <ref:2610.10904#pg15>. The reduction to reachability shows that this hardness is inherent in dynamic graph problems <ref:2610. p. 2

Where the paper says it

He introduced the multiphase problem, showed that it requires polynomial time under the 3SUM conjecture, and reduced it to dynamic reachability, shortest paths and subgraph connectivity, among others. Building on this, polynomial lower bounds for dynamic reachability and many other dynamic graph problems now follow from a handful of popular conjectures: the 3SUM and APSP conjectures and the Strong Exponential Time Hypothesis (SETH) [IPZ01, AW14], the hardness of combinatorial Boolean matrix multiplication [AW14], and the Online Matrix-Vector multiplication (OMv) conjecture [HKNS15].

10904#pg30>. The authors show that the framework can capture this hardness even for Boolean answers via Inner Product over F2 <ref:2610. p. 3
Where the paper says it

As discussed in [Ko26], it is likely the limit of the Chronogram framework, so Boolean problems can now be brought up to the best bounds that the Chronogram framework can give. Inner Product, however, is not known to capture natural dynamic graph problems: P˘atra¸scu’s reductions to reachability and related problems start from Disjointness.

10904#pg15>.

The Final Statement on Hardness

The paper proves that the multiphase problem of P˘atra¸scu with Disjointness requires super-logarithmic time for queries or updates <ref:2610.10904#pg15>. This is a fundamental result in dynamic data structure complexity. p. 1

Where the paper says it

Conditional lower bounds have been remarkably successful at charting which problems are as hard as which, but only unconditional lower bounds truly tell us that a problem is hard. This distinction recently became concrete: two of the three central conjectures of fine-grained complexity, the 3SUM and APSP conjectures, were refuted using AI [AW26, KL26], with a truly subquadratic algorithm for 3SUM and a truly subcubic one for APSP, and the result has been formalized in Lean.

The derived bound tq = omega(log n/ log(tuw))2 is the strongest unconditional lower bound known for any dynamic problem. This result is a major contribution to understanding the limits of dynamic data structure performance. p. 1
Where the paper says it

1 Introduction Dynamic graph problems, such as reachability, shortest paths and connectivity, are among the most natural and well-studied problems in theoretical computer science. A data structure maintains a graph on n vertices under edge updates, and answers queries about the current graph; in dynamic directed reachability, for instance, a query asks “is v reachable from u?

p. 1
Where the paper says it

1 Introduction Dynamic graph problems, such as reachability, shortest paths and connectivity, are among the most natural and well-studied problems in theoretical computer science. A data structure maintains a graph on n vertices under edge updates, and answers queries about the current graph; in dynamic directed reachability, for instance, a query asks “is v reachable from u?

p. 1
Where the paper says it

1 Introduction Dynamic graph problems, such as reachability, shortest paths and connectivity, are among the most natural and well-studied problems in theoretical computer science. A data structure maintains a graph on n vertices under edge updates, and answers queries about the current graph; in dynamic directed reachability, for instance, a query asks “is v reachable from u?

The Scope of Applicability

Theorem A.1 confirms that the derived bound applies to a wide variety of problems, including incremental directed reachability, undirected shortest paths, and subgraph connectivity <ref:2610. p. 4

Where the paper says it

A fully dynamic data structure also handles insertiononly sequences, so the bound applies to fully dynamic directed reachability as well. The same bound holds for incremental shortest paths and subgraph connectivity in undirected graphs, by the same reduction, and, with one more edge insertion per query, for incremental s-t reachability, #SSR, strong connectivity and cycle detection in directed graphs, and for incremental triangle detection in undirected graphs (Theorem A.

p. 4
Where the paper says it

A fully dynamic data structure also handles insertiononly sequences, so the bound applies to fully dynamic directed reachability as well. The same bound holds for incremental shortest paths and subgraph connectivity in undirected graphs, by the same reduction, and, with one more edge insertion per query, for incremental s-t reachability, #SSR, strong connectivity and cycle detection in directed graphs, and for incremental triangle detection in undirected graphs (Theorem A.

10904#pg31>. The result extends to problems like dynamic set disjointness and range mode <ref:2610. p. 0
Where the paper says it

Through his reductions, we obtain the same lower bound for dynamic data structures supporting reachability queries in n-node directed acyclic graphs under edge insertions, improving the Ωe(log3/2 n) lower bound of Larsen and Yu [SICOMP 2025], and matching the strongest lower bound known for any dynamic problem. The same bound holds for many other dynamic problems: in directed graphs, for incremental s-t reachability, strong connectivity and cycle detection; in undirected graphs, for incremental shortest paths, subgraph connectivity and triangle detection; and for dynamic set disjointness, range mode, and Langerman’s, Pagh’s and Erickson’s problems.

p. 0
Where the paper says it

Through his reductions, we obtain the same lower bound for dynamic data structures supporting reachability queries in n-node directed acyclic graphs under edge insertions, improving the Ωe(log3/2 n) lower bound of Larsen and Yu [SICOMP 2025], and matching the strongest lower bound known for any dynamic problem. The same bound holds for many other dynamic problems: in directed graphs, for incremental s-t reachability, strong connectivity and cycle detection; in undirected graphs, for incremental shortest paths, subgraph connectivity and triangle detection; and for dynamic set disjointness, range mode, and Langerman’s, Pagh’s and Erickson’s problems.

10904#pg29>. This broad applicability validates the power of the reduction technique used in the proof <ref:2610. p. 2
Where the paper says it

1 summarizes this progress. Each of these improvements may look marginal, but each required a conceptual shift in proof technique.

p. 2
Where the paper says it

1 summarizes this progress. Each of these improvements may look marginal, but each required a conceptual shift in proof technique.

10904#pg30>. The paper shows that these reductions work in the insert-only setting. p. 1
Where the paper says it

In this work, we prove an unconditional Ω(log n/ log log n) 2 lower bound for the multiphase problem of P˘atra¸scu [Pat10] with Disjointness, in its insert-only form (Theorem 1. Through his reductions, we obtain the same bound for dynamic directed reachability: every zero-error data structure with worst-case update time tu and expected query time tq has tq = Ω(log n/ log(tuw))2 , already for incremental reachability on depth-2 DAGs (Theorem 1.

The Bound on tq for Other Problems

Theorem A.2 establishes bounds for other problems like dynamic set disjointness and dynamic range mode, showing that tu + tq ≥ omega(log N/ log(tuw))2 <ref:2610. p. 2

Where the paper says it

It also holds for dynamic set disjointness, dynamic range mode, and Langerman’s, Pagh’s and Erickson’s problems (Theorems A. 1 Previous work Upper bounds.

p. 2
Where the paper says it

It also holds for dynamic set disjointness, dynamic range mode, and Langerman’s, Pagh’s and Erickson’s problems (Theorems A. 1 Previous work Upper bounds.

10904#pg29>. For these problems, the first bound holds with tq in place of tu + tq <ref:2610. p. 0
Where the paper says it

The same bound holds for many other dynamic problems: in directed graphs, for incremental s-t reachability, strong connectivity and cycle detection; in undirected graphs, for incremental shortest paths, subgraph connectivity and triangle detection; and for dynamic set disjointness, range mode, and Langerman’s, Pagh’s and Erickson’s problems. Ko [FOCS 2026] recently proved this bound for a variant of the multiphase problem with Inner Product in place of Disjointness, via a 2.

p. 0
Where the paper says it

The same bound holds for many other dynamic problems: in directed graphs, for incremental s-t reachability, strong connectivity and cycle detection; in undirected graphs, for incremental shortest paths, subgraph connectivity and triangle detection; and for dynamic set disjointness, range mode, and Langerman’s, Pagh’s and Erickson’s problems. Ko [FOCS 2026] recently proved this bound for a variant of the multiphase problem with Inner Product in place of Disjointness, via a 2.

10904#pg29>. This shows that the complexity is driven by the query time in many cases <ref:2610. p. 3
Where the paper says it

P˘atra¸scu and Demaine [PD06] replaced the epochs by a tree of time intervals and bounded the information transferred between adjacent intervals, which removes the log log n loss of the geometric epochs. Larsen [Lar12] showed, by cell sampling, that a query must read Ω(log n/ log(tuw)) cells from each epoch, not just one: if it read fewer, a small sample of the cells of an epoch would answer many queries, and hence encode the updates of that epoch in fewer bits than their entropy.

p. 3
Where the paper says it

P˘atra¸scu and Demaine [PD06] replaced the epochs by a tree of time intervals and bounded the information transferred between adjacent intervals, which removes the log log n loss of the geometric epochs. Larsen [Lar12] showed, by cell sampling, that a query must read Ω(log n/ log(tuw)) cells from each epoch, not just one: if it read fewer, a small sample of the cells of an epoch would answer many queries, and hence encode the updates of that epoch in fewer bits than their entropy.

10904#pg29>. The paper notes that if tu ≥ log2 N, there is nothing to prove for these problems, as log(tuw) = O(log log N) <ref:2610. p. 2
Where the paper says it

For problems whose queries return a single bit, such as reachability, there was no technique for proving even an ω(log n) lower bound until the breakthrough of Larsen, Weinstein and Yu [LWY20], who proved Ωe(log3/2 n). Building on their technique, Larsen and Yu [LY25] finally obtained the first super-logarithmic lower bound for a natural graph problem: for n-vertex DAGs under edge insertions, with worst-case update time tu, expected query time tq and word size w = Ω(log n), they show tq = Ωlog3/2 n/ log2 (tuw) [LY25, Theorem 1], so, for w = Θ(log n), max(tu, tq) = Ωe(log3/2 n).

10904#pg29>.

The Overall Implication

The overall implication of the paper is that dynamic graph problems require super-logarithmic time for queries or updates under the cell-probe model <ref:2610.10904#pg29>. The derived bound tq = omega(log n/ log(tuw))2 is the strongest unconditional lower bound known for any dynamic problem. This result is a major contribution to understanding the limits of dynamic data structure performance. It sets a new benchmark for complexity limits in this area. p. 1

Where the paper says it

Conditional lower bounds have been remarkably successful at charting which problems are as hard as which, but only unconditional lower bounds truly tell us that a problem is hard. This distinction recently became concrete: two of the three central conjectures of fine-grained complexity, the 3SUM and APSP conjectures, were refuted using AI [AW26, KL26], with a truly subquadratic algorithm for 3SUM and a truly subcubic one for APSP, and the result has been formalized in Lean.

The paper also notes that this result is likely the limit of the Chronogram framework for Boolean problems <ref:2610. p. 3
Where the paper says it

This bound matches the strongest lower bound known for any dynamic problem, which Larsen [Lar12] proved for a weighted problem whose queries return Θ(log n) bits. As discussed in [Ko26], it is likely the limit of the Chronogram framework, so Boolean problems can now be brought up to the best bounds that the Chronogram framework can give.

10904#pg15>.

Unconditional lower bounds are presented as eternal statements, contrasting them with conditional ones that can disappear overnight. This makes the unconditional result a statement of true hardness, regardless of future conjecture status <ref:2610.10904#pg3>. The paper stresses that this is why we must always strive for unconditional lower bounds <ref:2610.10904#pg2>. This provides a stronger guarantee of hardness than conditional arguments. p. 3

Where the paper says it

Despite this progress, it has long been conjectured that the true lower bound is much higher. Besides the conditional lower bounds above, P˘atra¸scu [Pat10] conjectured that the multiphase problem requires polynomial time, and identified a three-party communication game, now known as the multiphase communication game, whose hardness would imply this even in the cell-probe model, i.

The paper proves that the multiphase problem of P˘atra¸scu with Disjointness requires super-logarithmic time for queries or updates. The derived bound tq = omega(log n/ log(tuw))2 is the strongest unconditional lower bound known for any dynamic problem. This result is a major contribution to understanding the limits of dynamic data structure performance.

Theorem A.1 confirms that the derived bound applies to a wide variety of problems, including incremental directed reachability, undirected shortest paths, and subgraph connectivity <ref:2610.10904#pg31>. The result extends to problems like dynamic set disjointness and range mode <ref:2610.10904#pg29>. This broad applicability validates the power of the reduction technique used in the proof <ref:2610.10904#pg30>.

Theorem A.2 establishes bounds for other problems like dynamic set disjointness and dynamic range mode, showing that tu + tq ≥ omega(log N/ log(tuw))2 <ref:2610.10904#pg29>. For these problems, the first bound holds with tq in place of tu + tq <ref:2610.10904#pg29>. This shows that the complexity is driven by the query time in many cases <ref:2610.10904#pg29>.

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. Dynamic Graph Problem Solving for Reachability: The improved system can solve dynamic directed reachability queries on graphs with edge insertions in time proportional to log n/log log n squared, which is a significant improvement over previous bounds like max(tu, tq) = omega(log e 3/2 n).

  2. Hardness Verification for Dynamic Data Structures: The system can verify if a data structure is too good-to-be-true for dynamic problems by analyzing the probability of Bob accepting an answer, which provides a concrete lower bound on performance.

  3. Complexity Analysis of Multiphase Problems: The improved system can establish unconditional lower bounds for multiphase problems like Disjointness by leveraging the framework developed in Section 1.3, showing that verification in a 2.5-round communication game suffices to prove the bound unconditionally.

  4. Dynamic Set Disjointness Solver: The system can maintain and query dynamic set disjointness structures with an expected query time of O(tu + tq) or O(tq), matching the lower bounds established for this problem in Theorem A.2.

  5. Range Mode Query Optimization: For dynamic range mode, the system can answer queries about modes in subarrays by utilizing the reduction to multiphase Disjointness, achieving a query cost of O(tq) when tq is small relative to log n/log log n squared.

Abstract

We prove an unconditional Ω((n/ n) 2) lower bound on the maximum of the worst-case update time and expected query time for the insert-only version of Patrascu's multiphase Disjointness problem [STOC 2010]. The bound holds in the zero-error cell-probe model with logarithmic word size. Patrascu's reductions transfer it to directed reachability under edge insertions, already on directed acyclic graphs of depth 2. This improves the Ω(3/2 n) bound of Larsen and Yu [SICOMP 2025] to the quadratic-logarithmic scale previously attained for dynamic range counting and multiphase Inner Product. The bound also transfers to a broad collection of dynamic graph, algebraic, geometric, and string problems. We also obtain a separation between amortized and worst-case time for streaming regular-expression membership. For a simple family of expressions of maximum length M over a polynomial-size alphabet, a deterministic algorithm uses O(1) amortized time per symbol on every input stream, whereas every zero-error cell-probe algorithm with word size w=Θ(M) requires Ω((M/ M) 2) time on some symbol. The proof adapts Ko's 2.5-round multiphase communication framework [FOCS 2026] from Inner Product to Disjointness. Our main technical observation is that the protocol's verification step allows a one-sided corruption bound to replace the discrepancy property used for Inner Product.

Sources

Related papers