Cell-probe lower bounds for dynamic problems via a new communication model

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 I over [0,n] with integer coordinates, supporting the following operations: 1) insert(a, b), add an interval [a, b] to I, provided that a and b are integers in [0,n]; 2) delete(a, b), delete an (existing) interval [a, b] from I; 3) query(), return the total length of the union of all intervals in 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 Ω(nlogn) time in expectation. Interestingly, we use the sparse set disjointness protocol of Håstad and Wigderson 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.