  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 $\Omega(n\log n)$ time
in expectation. Interestingly, we use the sparse set disjointness protocol of
H\aa{}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.
