Bit-Probe Lower Bounds for Succinct Data Structures
Emanuele Viola · SIAM Journal on Computing · 2012
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 as follows: (i) To represent $n$ ternary values $t \in \{0,1,2\}^n$ in terms of $u$ bits $b \in \{0, 1\}^u$ while accessing a single value $t_i \in \{0,1,2\}$ 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ǎtraşcu (FOCS 2008), later refined with Dodis and Thorup (STOC 2010), where $u \leq (\log_2 3)n + n/2^{\Omega(q)}$. 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. (ii) To represent sets of size $n/3$ from a universe of $n$ elements in terms of $u$ bits $b \in \{0, 1\}^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$. Both results hold even if the probe locations are determined adaptively. Ours are the first lower bounds for these fundamental problems; we obtain them by drawing on ideas used in a lower bound for locally decodable codes by Shaltiel and the author [SIAM J. Comput., 39 (2010), pp. 3122--3154].