Set membership with two bit probes

We will consider the 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 vector in order to answer membership queries of the form ``Is x in S?'' by adaptively probing the bit vector at t places. Let s(m,n,t) be the minimum number of bits of storage needed for such a scheme. Alon and Feige showed that for t=2 (two bit probes), such schemes can be obtained from dense graphs with large girth. In particular, they showed that for n < log m, s(m,n,2) = O(m n log((log m) / n) / log m).

We improve their analysis and obtain a better upper bound and a corresponding lower bound.

Upper bound: There is a constant C>0, such that for all large m, s(m,n,2) <= C  m^{1-1/(4n+1)}.

Lower bound: There is a constant D>0, such that for n>=4 and all large m, we have s(m,n,2) >= D  m^{1-{4}{n}}.

(This is joint work with Mohit Garg.)