Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with dictionary:
TR09-005 | 7th December 2008
Emanuele Viola

Bit-Probe Lower Bounds for Succinct Data Structures

We prove lower bounds on the redundancy necessary to
represent a set $S$ of objects using a number of bits
close to the information-theoretic minimum $\log_2 |S|$,
while answering various queries by probing few bits. Our
main results are:

\item To represent $n$ ternary values $t \in
\zot^n$ in ... more >>>

TR20-003 | 15th January 2020
Giuseppe Persiano, Kevin Yeo

Tight Static Lower Bounds for Non-Adaptive Data Structures

Revisions: 1

In this paper, we study the static cell probe complexity of non-adaptive data structures that maintain a subset of $n$ points from a universe consisting of $m=n^{1+\Omega(1)}$ points. A data structure is defined to be non-adaptive when the memory locations that are chosen to be accessed during a query depend ... more >>>

ISSN 1433-8092 | Imprint