Bit-probe lower bounds for succinct data structures
From MaRDI portal
Publication:5172742
DOI10.1145/1536414.1536480zbMath1304.68035MaRDI QIDQ5172742
Publication date: 4 February 2015
Published in: Proceedings of the forty-first annual ACM symposium on Theory of computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/1536414.1536480
lower bound; succinct data structure; membership query; logarithmic form; dictionary; cell-probe; bit-probe; ternary value
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68P05: Data structures