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 ( n log n log log n 2 ) cell-probe lower bound for the dynamic 2D weighted orthogonal range counting problem ( 2D-ORC ) with n pol y log n updates and n queries, that holds even for data structures with exp ( − ( 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 (( log n log log n ) 2 ) lower bound for the \emph{static} 3D-ORC 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 ( log n ) barrier for static data structures.