To print higher-resolution math symbols, click the
Hi-Res Fonts for Printing button on the jsMath control panel.

jsMath
Loading jsMath...
Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > DYNAMIC CELL-PROBE LOWER BOUNDS:
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