4 papers
Lower Bounds for Restricted Schemes in the Two-Adaptive Bitprobe Model
Sreshth Aggarwal, Deepanjan Kesh, Divyam Singal
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 Mathema…
Improved Bounds for Two Query Adaptive Bitprobe Schemes Storing Five Elements
Mirza Galib Anwarul Husain Baig, Deepanjan Kesh
In this paper, we study two-bitprobe adaptive schemes storing five elements. For these class of schemes, the best known lower bound is m^{1/2} due to Alon and Feige [SODA 2009]. Re…
An Improved Scheme in the Two Query Adaptive Bitprobe Model
Mirza Galib Anwarul Husain Baig, Deepanjan Kesh, Chirag Sodani
In this paper, we look into the adaptive bitprobe model that stores subsets of size at most four from a universe of size m, and answers membership queries using two bitprobes. We p…
A Two Query Adaptive Bitprobe Scheme Storing Five Elements
Mirza Galib Anwarul Husain Baig, Deepanjan Kesh, Chirag Sodani
We are studying the adaptive bitprobe model to store an arbitrary subset S of size at most five from a universe U of size m and answer the membership queries of the form "Is x in S…