Tight dynamic problem lower bounds from generalized BMM and OMv

Popular fine-grained hypotheses have been successful in proving conditional lower bounds for many dynamic problems. Two of the most widely applicable hypotheses in this context are the combinatorial Boolean Matrix Multiplication (BMM) hypothesis and the closely-related Online Matrix Vector Multiplication (OMv) hypothesis. The main theme of this paper is using k-dimensional generalizations of these two hypotheses 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(n 2/3-ε ) update time and O(n 2/3-ε ) query time for any ε > 0, matching the known upper bounds for this problem. Previous lower bounds only ruled out algorithms with O(n 1/2-ε ) update and query time under the OMv hypothesis.

• The Dynamic Subgraph Connectivity problem on undirected graphs with m edges has no combinatorial algorithms with poly(m) pre-processing time, O(m 2/3-ε ) update time and O(m 1-ε ) query time for ε > 0, matching the upper bound given by Chan, Pătraşcu, and Roditty [SICOMP'11], and improving the previous update time lower bound (based on OMv) with exponent 1/2. Other examples include tight combinatorial lower bounds for Dynamic 2D Orthogonal Range Color Counting, Dynamic 2-Pattern Document Retrieval, and Dynamic Range Mode in higher dimensions.

Furthermore, we propose the OuMv k 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(n 1-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.