Theory of Computing Seminar

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.)