Revisiting Non-Adaptive Set Membership Schemes: Removing the Logarithmic Factor
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.