Bit-probe lower bounds for succinct data structures

DOI10.1145/1536414.1536480zbMath1304.68035OpenAlexW1999560384MaRDI QIDQ5172742

Emanuele Viola

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

zbMATH Keywords

lower boundsuccinct data structuremembership querylogarithmic formdictionarycell-probebit-probeternary value

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Data structures (68P05)

This page was built for publication: Bit-probe lower bounds for succinct data structures