English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

This paper develops a new technique for proving amortized, randomizedcell-probe lower bounds on dynamic data structure problems. We introduce a newrandomized nondeterministic four-party communication model that enables"accelerated", error-preserving simulations of dynamic data structures.  We use this technique to prove an $\Omega(n(\log n/\log\log n)^2)$ cell-probelower bound for the dynamic 2D weighted orthogonal range counting problem(2D-ORC) with $n/\mathrm{poly}\log n$ updates and $n$ queries, that holds evenfor data structures with $\exp(-\tilde{\Omega}(n))$ success probability. Thisresult not only proves the highest amortized lower bound to date, but is alsotight in the strongest possible sense, as a matching upper bound can beobtained by a deterministic data structure with worst-case operational time.This is the first demonstration of a "sharp threshold" phenomenon for dynamicdata structures.  Our broader motivation is that cell-probe lower bounds for exponentiallysmall success facilitate reductions from dynamic to static data structures. Asa proof-of-concept, we show that a slightly strengthened version of our lowerbound would imply an $\Omega((\log n /\log\log n)^2)$ lower bound for thestatic 3D-ORC problem with $O(n\log^{O(1)}n)$ space. Such result would give anear quadratic improvement over the highest known static cell-probe lowerbound, and break the long standing $\Omega(\log n)$ barrier for static datastructures.

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