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