Bit-probe lower bounds for succinct data structures

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: To represent n ternary values t ∈ {0,1,2} n in terms of u bits b ∈ {0,1} u while accessing a single value t i ∈ {0,1,2} by probing q bits of b, one needs u ≥ (log 2 3)n + n/2 O(q) . This matches an exciting representation by Patrascu (FOCS 2008), later refined with Thorup, where u ≤ (log_2 3)n + n/2 Ω(q) . We also note that results on logarithmic forms imply the lower bound u ≥ (log 2 3)n + n/log O(1) n if we access t i by probing one cell of log n bits. To represent sets of size n/3 from a universe of n elements in terms of u bits b ∈ {0,1} u while answering membership queries by probing q bits of b, one needs u ≥ log 2 n/(n/3) + n/2 O(q) - log n. 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.

Authors

• Emanuele Viola

Keywords

• bit-probe
• cell-probe
• dictionary
• logarithmic form
• lower bound
• membership query
• succinct data structure
• ternary value