Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR16-054 | 11th April 2016 18:16

Amortized Dynamic Cell-Probe Lower Bounds from Four-Party Communication



This paper develops a new technique for proving amortized, randomized cell-probe lower bounds on dynamic
data structure problems. We introduce a new randomized nondeterministic four-party communication model
that enables "accelerated", error-preserving simulations of dynamic data structures.

We use this technique to prove an $\Omega(n\left(\log n/\log\log n\right)^2)$ cell-probe lower bound for the
dynamic 2D weighted orthogonal range counting problem ($\bf $2D-ORC$\rm$) with $n/\mathrm{poly}\log n$ updates
and $n$ queries, that holds even for data structures with $\exp(-\tilde{\Omega}(n))$ success probability.
This result not only proves the highest amortized lower bound to date, but is also tight in the strongest possible
sense, as a matching upper bound can be obtained by a deterministic data structure with worst-case operational
time. This is the first demonstration of a "sharp threshold" phenomenon for dynamic data structures.

Our broader motivation is that cell-probe lower bounds for exponentially small success facilitate \emph{reductions
from dynamic to static} data structures. As a proof-of-concept, we show that a slightly strengthened version of our
lower bound would imply an $\Omega((\log n /\log\log n)^2)$ lower bound for the \emph{static} $\bf $3D-ORC$\rm$ problem
with $O(n\log^{O(1)}n)$ space. Such result would give a near quadratic improvement over the highest known static
cell-probe lower bound, and break the long standing $\Omega(\log n)$ barrier for static data structures.

ISSN 1433-8092 | Imprint