Room 327

Set membership with two bit probes

Venkatesh Raman

IMSc Chennai

We consider the following problem. Given a set S of n elements from a universe of size m, what is the minimum number of bits required to represent it so that membership query (`given an element from the universe, is it in the set') can be answered in at most two probes to the structure. We will primarily discuss upper bounds for various values of n starting from 1.