__
TR09-005 | 7th December 2008 00:00
__

#### Bit-Probe Lower Bounds for Succinct Data Structures

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