Lower Bounds for Restricted Schemes in the Two-Adaptive Bitprobe Model

2022/04/07 by Aggarwal, Sreshth, Kesh, Deepanjan, Singal, Divyam
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.2204.03266

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 Ω(m^(2)/(3)) 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 Ω(((m)/(n))^{1 - (1)/(\lfloor n / 4 \rfloor + 2)}).

Related

• An Improved Scheme in the Two Query Adaptive Bitprobe Model
• Improved Bounds for Two Query Adaptive Bitprobe Schemes Storing Five\n Elements
• A Two Query Adaptive Bitprobe Scheme Storing Five Elements
• Set membership with non-adaptive bit probes
• Set Membership with a Few Bit Probes