Are bitvectors optimal?

DOI10.1145/335305.335357MaRDI QIDQ3192013zbMATH OpenOpenAlexFDO

Authors

Publication date 26 September 2014

Published in Proceedings of the thirty-second annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/335305.335357

Mathematics Subject Classification ID

Searching and sorting (68P10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Are Bitvectors Optimal?
• Set membership with a few bit probes
• Data structures for storing small sets in the bitprobe model
• Set membership with non-adaptive bit probes

Cited in

(11)

• Storing information with extractors.
• The quantum complexity of set membership
• On the bitprobe complexity of two probe adaptive schemes
• The cell probe complexity of succinct data structures
• Efficient and error-correcting data structures for membership and polynomial evaluation
• Are Bitvectors Optimal?
• Membership in Constant Time and Almost-Minimum Space
• Flavors of compressive sensing
• Set membership with a few bit probes
• Exponential lower bound for 2-query locally decodable codes via a quantum argument
• The Gelfand widths of \(\ell_p\)-balls for \(0 < p \leq 1\)

This page was built for publication: Are bitvectors optimal?

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3192013)