#### 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