3 papers
cs.DS2019
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…
cs.DS2018
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…
cs.DS2018
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…