Title
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 I over [0, n] with integer coordinates, supporting the following operations: 

- insert(a, b): add an interval [a, b] to I, provided that a and b are integers in [0, n]; 

- delete(a, b): delete a (previously inserted) interval [a, b] from I; 

- 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 Omega(n log n) time in expectation. Interestingly, we use the sparse set disjointness protocol of Hastad 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.