Set membership with non-adaptive bit probes

Mohit Garg, Jaikumar Radhakrishnan

We consider the non-adaptive bit-probe complexity of the set membership problem, where a set S of size at most n from a universe of size m is to be represented as a short bit vecto…