## Speaker:

Saswata Shannigrahi
School of Technology and Computer Science
Tata Institute of Fundamental Research
Homi Bhabha R

## Time:

Friday, 3 September 2010 (All day)

## Venue:

- A-212 (STCS Seminar Room)

We study the following set membership problem in the bitprobe model: Given a set S from a finite universe U , represent it in memory so that membership queries of the form Is x in S? can be answered with a small number of bitprobes. We obtain explicit schemes that come close to the information theoretic lower bound of Buhrman et al. [STOC 2000, SICOMP 2002] and improve the results of Radhakrishnan et al. [ESA 2001] when the size of sets and the number of probes is small.

We show that any scheme that stores sets of size two from a universe of size m and answers membership queries using two bitprobes requires space Î©(m^(4/7)). The previous best lower bound was Î©(m^(1/2}). This is the first instance where the information theoretic lower bound is found to be not tight for adaptive schemes.

We show that any non-adaptive three probe scheme for storing sets of size two from a universe of size m requires Î©(m^(1/2}) bits of memory. This extends a result of Alon and Feige [SODA 2009] to small sets (to be presented in ESA 2010 joint work with Jaikumar Radhakrishnan and Smit Shah).