Revisiting Non-Adaptive Set Membership Schemes: Removing the Logarithmic Factor

Mirza Galib Anwarul Husain Baig, Aman Kumar, Pawan Kumar Saw +1

We study non-adaptive bit-probe schemes for static set membership. Each query reads a fixed number of bits and answers by strict majority. We revisit the random bipartite-graph con…