MADALGO Theory Seminar
MADALGO Seminar: Huacheng Yu (Stanford University): "Cell-probe Lower Bounds for Dynamic Problems via a New Communication Model"
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.