Abstract:
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 terms of $u$ bits $b \in \zo^u$ while accessing a single value $t_i \in \zot$ by probing $q$ bits of $b$, one needs $$u \geq (\log_2 3)n + n/2^{O(q)}.$$ This matches an exciting representation by P{\v a}tra{\c s}cu (FOCS 2008) where $u \leq (\log_2 3)n + n/2^{q^{\Omega(1)}}$. We also note that results on logarithmic forms imply the lower bound $u \geq (\log_2 3)n + n/\log^{O(1)} n$ if we access $t_i$ by probing one cell of $\log n$ bits. \item To represent sets of size $n/3$ from a universe of $n$ elements in terms of $u$ bits $b \in \zo^u$ while answering membership queries by probing $q$ bits of $b$, one needs $$u \geq \log_2 \binom{n}{n/3} + n/2^{O(q)} - \log n.$$ \end{itemize} Both results above hold even if the probe locations are determined adaptively. Ours are the first lower bounds for these fundamental problems; we obtain them drawing on ideas used in lower bounds for locally decodable codes.