Title: Cell-Probe Lower Bounds from Online Communication Complexity,
Abstract: In this work, we introduce an online model for communication complexity.
Analogous to how online algorithms receive their input piece-by-piece, our
model presents one of the players, Bob, his input piece-by-piece, and has the
players Alice and Bob cooperate to compute a result each time before the next
piece is revealed to Bob. This model has a closer and more natural
correspondence to dynamic data structures than classic communication models do,
and hence presents a new perspective on data structures.
We first present a tight lower bound for the online set intersection problem
in the online communication model, demonstrating a general approach for proving
online communication lower bounds. The online communication model prevents a
batching trick that classic communication complexity allows, and yields a
stronger lower bound. We then apply the online communication model to prove
data structure lower bounds for two dynamic data structure problems: the Group
Range problem and the Dynamic Connectivity problem for forests. Both of the
problems admit a worst case $O(\log n)$-time data structure. Using online
communication complexity, we prove a tight cell-probe lower bound for each:
spending $o(\log n)$ (even amortized) time per operation results in at best an
$\exp(-\delta^2 n)$ probability of correctly answering a
$(1/2+\delta)$-fraction of the $n$ queries.