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

Omri Weinstein, Huacheng Yu

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 fou…