Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Dynamic cell-probe lower bounds:
TR16-054 | 11th April 2016
Omri Weinstein, Huacheng Yu

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

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 ... more >>>

TR22-122 | 29th August 2022
Young Kun Ko

Efficient Linearization Implies the Multiphase Conjecture

The main motivation for studying linear data structures and circuits is the intuition that non-linear advice cannot help in computing a linear operator. Jukna and Schnitger formalized this as a conjecture which states that all circuits computing a linear operator can be ``linearized," with only a constant size blow-up. We ... more >>>

ISSN 1433-8092 | Imprint