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