Set membership with non-adaptive bit probes

2016/12/30 by Garg, Mohit, Radhakrishnan, Jaikumar
#68P05 #68P20 #68P30 #Data Structures and Algorithms (cs.DS) #E.1 #E.4 #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.1612.09388

Abstract

We consider the non-adaptive bit-probe complexity of the set membership problem, where a set S of size at most n from a universe of size m is to be represented as a short bit vector in order to answer membership queries of the form "Is x in S?" by non-adaptively probing the bit vector at t places. Let s_N(m,n,t) be the minimum number of bits of storage needed for such a scheme. In this work, we show existence of non-adaptive and adaptive schemes for a range of t that improves an upper bound of Buhrman, Miltersen, Radhakrishnan and Srinivasan (2002) on s_N(m,n,t). For three non-adaptive probes, we improve the previous best lower bound on s_N(m,n,3) by Alon and Feige (2009).

Related

• Set Membership with a Few Bit Probes
• Set membership with two classical and quantum bit probes
• Pseudo-random graphs and bit probe schemes with one-sided error
• An Improved Scheme in the Two Query Adaptive Bitprobe Model
• Tight Static Lower Bounds for Non-Adaptive Data Structures