Unconditional Boolean Dynamic Lower Bounds from Disjointness
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 Ω((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. 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. 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.Where the paper says it
Where the paper says it
Where the paper says it
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 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. Ω((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. Ω((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.Where the paper says it
Where the paper says it
Where the paper says it
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 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. 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. 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. 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.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
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 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. Yet Bob learns, with probability n
−o(1), that SQ and X are disjoint. This is what makes the
protocol too good to exist.Where the paper says it
Where the paper says it
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 A nearly monochromatic rectangle (Section 3. By Pinsker’s inequality, replacing this
distribution by the product of its two marginals moves little mass. 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. 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.Where the paper says it
Where the paper says it
Where the paper says it
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 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. 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).Where the paper says it
Where the paper says it
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 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. 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.Where the paper says it
Where the paper says it
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 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.Where the paper says it
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 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. ∗Department of Computer Science and Engineering, Pennsylvania State University, University Park, PA, USA. edu
1
arXiv:2610. • Merlin’s message U is the list of all cells written in epochs i, . , 1, with their final contents.Where the paper says it
Where the paper says it
Where the paper says it
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 Ω((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. 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. 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).Where the paper says it
Where the paper says it
Where the paper says it
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 Conditional lower bounds. To argue that these algorithms are close to optimal, a series of
conditional lower bounds has been developed since 2010. 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. ∗Department of Computer Science and Engineering, Pennsylvania State University, University Park, PA, USA. edu
1
arXiv:2610. 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.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
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 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. 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
.Where the paper says it
Where the paper says it
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 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. 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). 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. 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).Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
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 Ω((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. Ω((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. Ω((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. Ω((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. 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). 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.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
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 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.Where the paper says it
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 1 summarizes this progress. Each of these improvements may look marginal, but each required a conceptual shift in proof
technique. 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 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. 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.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
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 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. 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.Where the paper says it
Where the paper says it
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 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. 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.Where the paper says it
Where the paper says it
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 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. 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.Where the paper says it
Where the paper says it
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 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. ∗Department of Computer Science and Engineering, Pennsylvania State University, University Park, PA, USA. edu
1
arXiv:2610.Where the paper says it
Where the paper says it
The Importance of Unconditional Bounds
Unconditional lower bounds are emphasized as being 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. 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.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. 1Where the paper says it
Where the paper says it
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 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. 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].Where the paper says it
Where the paper says it
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 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). 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.Where the paper says it
Where the paper says it
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 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. 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. 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.Where the paper says it
Where the paper says it
Where the paper says it
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 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]. 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.Where the paper says it
Where the paper says it
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 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. 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? 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? 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?Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
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 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. 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. 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. 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. 1 summarizes this progress. Each of these improvements may look marginal, but each required a conceptual shift in proof
technique. 1 summarizes this progress. Each of these improvements may look marginal, but each required a conceptual shift in proof
technique. 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.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
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 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. 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. 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. 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˘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˘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. 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).Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
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 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. 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.Where the paper says it
Where the paper says it
Unconditional lower bounds are presented as 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.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. 3Where the paper says it
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
-
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).
-
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.
-
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.
-
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.
-
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
- PHastR: Faster Minimal Perfect Hashing with Rotated Layouts
- Fine-Grained Complexity of Approximating Vector Knapsack: A Faster Algorithm and Equivalence with k-SUM in 2D
- Polynomial-time computation of p-contraction fixed points for even p
- Separations Between Submodular-Like Graph Widths
- Bounded Integer Programming in Almost N 2d Time
- Fast Odd-Permutation Sums in Characteristic Two and Shortest Even Directed Cycles