Cell-probe Lower Bounds for Dynamic Problems via a New Communication Model

Abstract

In this paper, we develop a new communication model to prove a data structure lower bound for the dynamic interval union problem. The problem is to maintain a multiset of intervals $\mathcal{I}$ over $[0, n]$ with integer coordinates, supporting the following operations: - insert(a, b): add an interval $[a, b]$ to $\mathcal{I}$, provided that $a$ and $b$ are integers in $[0, n]$; - delete(a, b): delete a (previously inserted) interval $[a, b]$ from $\mathcal{I}$; - query(): return the total length of the union of all intervals in $\mathcal{I}$. It is related to the two-dimensional case of Klee's measure problem. We prove that there is a distribution over sequences of operations with $O(n)$ insertions and deletions, and $O(n^{0.01})$ queries, for which any data structure with any constant error probability requires $Ω(n\log n)$ time in expectation. Interestingly, we use the sparse set disjointness protocol of Håstad and Wigderson [ToC'07] to speed up a reduction from a new kind of nondeterministic communication games, for which we prove lower bounds. For applications, we prove lower bounds for several dynamic graph problems by reducing them from dynamic interval union.