Lower bounds for restricted schemes in the two-adaptive bitprobe model

DOI10.1007/978-3-031-06678-8_3MaRDI QIDQ2169936zbMATH OpenOpenAlexFDO

Authors S. Aggarwal, Deepanjan Kesh, Divyam Singal

Publication date 30 August 2022

Full work available at URL https://arxiv.org/abs/2204.03266

Mathematics Subject Classification ID

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

Abstract: In the adaptive bitprobe model answering membership queries in two bitprobes, we consider the class of restricted schemes as introduced by Kesh and Sharma (Discrete Applied Mathematics 2021). In that paper, the authors showed that such restricted schemes storing subsets of size 2 require $Omega(m^{f}rac23)$ space. In this paper, we generalise the result to arbitrary subsets of size $n$, and prove that the space required for such restricted schemes will be $Omega(left(fracmnight{)}^{1-frac1lfloorn/4floor+2})$.

Recommendations

• On the bitprobe complexity of two probe adaptive schemes storing two elements
• An improved scheme in the two query adaptive bitprobe model
• On the bitprobe complexity of two probe adaptive schemes
• On adaptive bitprobe schemes for storing two elements
• Data structures for storing small sets in the bitprobe model

Cites work

• A Survey of Data Structures in the Bitprobe Model
• 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 bitprobe complexity of two probe adaptive schemes storing two elements
• Set membership with a few bit probes
• Space Complexity of Two Adaptive Bitprobe Schemes Storing Three Elements
• Two new schemes in the bitprobe model

Cited in

(5)

• Tight bounds for double coverage against weak adversaries
• On the bitprobe complexity of two probe adaptive schemes
• An improved scheme in the two query adaptive bitprobe model
• On the bitprobe complexity of two probe adaptive schemes storing two elements
• Tight Bounds for Double Coverage Against Weak Adversaries

This page was built for publication: Lower bounds for restricted schemes in the two-adaptive bitprobe model

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