# Tight Dynamic Problem Lower Bounds from Generalized BMM and OMv

arXiv: https://arxiv.org/abs/2202.11250 · HTML: https://mlsanity.com/paper/2202.11250/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Feb 2022.

## Built on by (most cited first, 2 of 2)

- [The Structural Complexity of Matrix-Vector Multiplication](https://mlsanity.com/paper/2502.21240/) (2025)
- [Connectivity Oracles for Predictable Vertex Failures](https://mlsanity.com/paper/2312.08489/) (2023)

## Abstract (arXiv)

The main theme of this paper is using k-dimensional generalizations of the combinatorial Boolean Matrix Multiplication (BMM) hypothesis and the closely-related Online Matrix Vector Multiplication (OMv) hypothesis to prove new tight conditional lower bounds for dynamic problems. The combinatorial k-Clique hypothesis, which is a standard hypothesis in the literature, naturally generalizes the combinatorial BMM hypothesis. In this paper, we prove tight lower bounds for several dynamic problems under the combinatorial k-Clique hypothesis. For instance, we show that: * The Dynamic Range Mode problem has no combinatorial algorithms with poly(n) pre-processing time, O(n2/3-ε) update time and O(n2/3-ε) query time for any ε > 0, matching the known upper bounds for this problem. Previous lower bounds only ruled out algorithms with O(n1/2-ε) update and query time under the OMv hypothesis. Other examples include tight combinatorial lower bounds for Dynamic Subgraph Connectivity, Dynamic 2D Orthogonal Range Color Counting, Dynamic 2-Pattern Document Retrieval, and Dynamic Range Mode in higher dimensions. Furthermore, we propose the OuMvk hypothesis as a natural generalization of the OMv hypothesis. Under this hypothesis, we prove tight lower bounds for various dynamic problems. For instance, we show that: * The Dynamic Skyline Points Counting problem in (2k-1)-dimensional space has no algorithm with poly(n) pre-processing time and O(n1-1/k-ε) update and query time for ε > 0, even if the updates are semi-online. Other examples include tight conditional lower bounds for (semi-online) Dynamic Klee's measure for unit cubes, and high-dimensional generalizations of Erickson's problem and Langerman's problem.