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 number of exceptional elements. This makes a separate probabilistic estimate for exceptional elements unnecessary. A detailed union-bound calculation then gives, for every fixed $t\ge 5$, a logarithm-free existence bound of $O_t(m^{1\mathrm{/}c}{n}^{1-1\mathrm{/}c})$, where $c=\lfloor (t-1)\mathrm{/}2\rfloor$. For odd $t$, this removes the logarithmic factor from the general upper bound of Garg and Radhakrishnan [STACS, 2017].