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

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