Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Chebychev polynomials :
TR17-047 | 10th March 2017
Kasper Green Larsen, Omri Weinstein, Huacheng Yu

Crossing the Logarithmic Barrier for Dynamic Boolean Data Structure Lower Bounds

This paper proves the first super-logarithmic lower bounds on the cell probe complexity of dynamic \emph{boolean} (a.k.a. decision) data structure problems, a long-standing milestone in data structure lower bounds.

We introduce a new method for proving dynamic cell probe lower bounds and use it to prove a $\tilde{\Omega}(\log^{1.5} ... more >>>

ISSN 1433-8092 | Imprint