ECCC-Report TR16-054https://eccc.weizmann.ac.il/report/2016/054Comments and Revisions published for TR16-054en-usTue, 12 Apr 2016 20:44:20 +0300
Paper TR16-054
| Amortized Dynamic Cell-Probe Lower Bounds from Four-Party Communication |
Omri Weinstein,
Huacheng Yu
https://eccc.weizmann.ac.il/report/2016/054This 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. Tue, 12 Apr 2016 20:44:20 +0300https://eccc.weizmann.ac.il/report/2016/054