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₂ |S|, while answering various queries by probing few bits. Our main results are: To represent n ternary values t ∈ {0,1,2}ⁿ 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₂ 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₂ 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₂ 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.

REFERENCES

• 1: A. Baker. Transcendental number theory. Cambridge Mathematical Library. Cambridge University Press, second edition, 1990.
• 2: A. Baker and G. Wüstholz. Logarithmic forms and Diophantine geometry, volume 9 of New Mathematical Monographs. Cambridge University Press, 2007.
• 3: H. Buhrman , P. B. Miltersen , J. Radhakrishnan , S. Venkatesh, Are Bitvectors Optimal?, SIAM Journal on Computing, v.31 n.6, p.1723-1744, 2002 [doi>10.1137/S0097539702405292]
• 4: Thomas M. Cover , Joy A. Thomas, Elements of Information Theory (Wiley Series in Telecommunications and Signal Processing), Wiley-Interscience, 2006
• 5: J. Edmonds, R. Impagliazzo, S. Rudich, and J. Sgall. Communication complexity towards lower bounds on circuit depth. Computational Complexity, 10(3):210--246, 2001.
• 6: Richard F. Geary , Naila Rahman , Rajeev Raman , Venkatesh Raman, A simple optimal representation for balanced parentheses, Theoretical Computer Science, v.368 n.3, p.231-246, December, 2006 [doi>10.1016/j.tcs.2006.09.014]
• 7: Alexander Golynski, Cell probe lower bounds for succinct data structures, Proceedings of the Nineteenth Annual ACM -SIAM Symposium on Discrete Algorithms, p.625-634, January 04-06, 2009, New York, New York
• 8: Thomas Holenstein, Parallel repetition: simplifications and the no-signaling case, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11-13, 2007, San Diego, California, USA [doi>10.1145/1250790.1250852]
• 9: P. B. Miltersen. Cell probe complexity -- a survey. In 19th Conference on the Foundations of Software Technology and Theoretical Computer Science (FSTTCS), 1999. Advances in Data Structures Workshop, 1999.
• 10: M. Minsky and S. Papert. Perceptrons. MIT Press, Cambridge, MA, 1969.
• 11: Michael Mitzenmacher, Compressed bloom filters, Proceedings of the twentieth annual ACM symposium on Principles of distributed computing, p.144-150, August 2001, Newport, Rhode Island, United States [doi>10.1145/383962.384004]
• 12: Rasmus Pagh, Low Redundancy in Static Dictionaries with Constant Query Time, SIAM Journal on Computing, v.31 n.2, p.353-363, 2001 [doi>10.1137/S0097539700369909]
• 13: Rasmus Pagh, On the cell probe complexity of membership and perfect hashing, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.425-432, July 2001, Hersonissos, Greece [doi>10.1145/380752.380836]
• 14: Mihai Patrascu, Succincter, Proceedings of the 2008 49th Annual IEEE Symposium on Foundations of Computer Science, p.305-313, October 25-28, 2008 [doi>10.1109/FOCS.2008.83]
• 15: Mihai Patracu , Corina E. Tarnia, On dynamic bit-probe complexity, Theoretical Computer Science, v.380 n.1-2, p.127-142, July 2007 [doi>10.1016/j.tcs.2007.02.058]
• 16: M. Patrascu and M. Thorup. Succincter-er, 2009. Manuscript.
• 17: Ran Raz, A Parallel Repetition Theorem, SIAM Journal on Computing, v.27 n.3, p.763-803, June 1998 [doi>10.1137/S0097539795280895]
• 18: Ronen Shaltiel , Emanuele Viola, Hardness amplification proofs require majority, Proceedings of the 40th annual ACM symposium on Theory of computing, May 17-20, 2008, Victoria, British Columbia, Canada [doi>10.1145/1374376.1374461]
• 19: Emanuele Viola , Salil P. Vadhan, The complexity of hardness amplification and derandomization, Harvard University, Cambridge, MA, 2006

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.3 Tradeoffs among Complexity Measures

Additional Classification:
  E. Data
  E.1 DATA STRUCTURES

General Terms:
Algorithms, Theory

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