# Theory of Computing Seminar

Friday
May 1, 2015
12:00 PM

**Set membership with two bit probes **

**Speaker:**Jaikumar Radhakrishnan, Tata Institute for Fundamental Research (TBC)

**Location:**Annenberg 213

**Abstract:**

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

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

**Series**Theory of Computing Seminar Series

**Contact:** Thomas Vidick vidick@cms.caltech.edu