Space Complexity of Two Adaptive Bitprobe Schemes Storing Three Elements

DOI10.4230/LIPICS.FSTTCS.2018.12MaRDI QIDQ5090947zbMATH OpenOpenAlexFDO

Authors Deepanjan Kesh

Publication date 21 July 2022

Full work available at URL https://doi.org/10.4230/LIPIcs.FSTTCS.2018.12

zbMATH Keywords

bitprobe modeldata structureslower boundset membership problem

Mathematics Subject Classification ID

Mathematical aspects of software engineering (specification, verification, metrics, requirements, etc.) (68N30) Theory of computing (68Qxx)

Recommendations

• On the bitprobe complexity of two probe adaptive schemes storing two elements
• On adaptive bitprobe schemes for storing two elements
• Set membership with non-adaptive bit probes
• Data structures for storing small sets in the bitprobe model
• A two query adaptive bitprobe scheme storing five elements

Cites work

• Data structures for storing small sets in the bitprobe model
• scientific article; zbMATH DE number 1875423 (Why is no real title available?)
• Improved explicit data structures in the bitprobe model
• On the power of two, three and four probes
• Set membership with a few bit probes
• Two new schemes in the bitprobe model

Cited in

(3)

• Storing four elements in the two query bitprobe model
• Lower bounds for restricted schemes in the two-adaptive bitprobe model
• Improved Explicit Data Structures in the Bit-Probe Model Using Error-Correcting Codes

This page was built for publication: Space Complexity of Two Adaptive Bitprobe Schemes Storing Three Elements

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