Emanuele Viola

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:

\begin{itemize}

\item To represent $n$ ternary values $t \in

\zot^n$ in ...
more >>>

Emanuele Viola, Emanuele Viola

We prove that to store n bits x so that each

prefix-sum query Sum(i) := sum_{k < i} x_k can be answered

by non-adaptively probing q cells of log n bits, one needs

memory > n + n/log^{O(q)} n.

Our bound matches a recent upper bound of n +

n/log^{Omega(q)} ...
more >>>