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

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