pipette
ESEspañol

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

Mirza Galib Anwarul Husain Baig, Aman Kumar, Pawan Kumar Saw, and Vikash Tripathi

Preprint

In the authors' words

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 number of exceptional elements. This makes a separate probabilistic estimate for exceptional elements unnecessary. A detailed union-bound calculation then gives, for every fixed , a logarithm-free existence bound of , where . For odd , this removes the logarithmic factor from the general upper bound of Garg and Radhakrishnan [STACS, 2017].

Main resultLimitation the authors admit

Appeared: Thursday, October 15. arXiv. Preprint, not yet peer-reviewed.