Preprint
Oct 2026
Revisiting Non-Adaptive Set Membership Schemes: Removing the Logarithmic Factor
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 construction of Garg and Radhakrishnan [STACS, 2017]. The main observation is that a slightly stronger expansion property already bounds the nu...
Mirza Galib Anwarul Husain Baig, Aman Kumar, Pawan Kumar Saw et al.
· 0 citations