TR16-054 Authors: Omri Weinstein, Huacheng Yu

Publication: 12th April 2016 20:44

Downloads: 686

Keywords:

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.