Theoretical Statistics and Mathematics Unit, ISI Delhi

March 1, 2012 (Thursday) ,
3:30 PM at Webinar

Speaker:
Niranjan Balachandran,
Indian Institute of Technology, Bombay

Title:
Storing small sets efficiently in the bit probe model with 2 adaptive probes

Abstract of Talk

The problem of storing small sets efficiently - first studied by
Buhrman et al - is essentially the following: Given a universal
set U of size m, we are interested in storing (as bits) small
subsets S of U (subsets of size at most t for some fixed t) so
that any query of the form "Is x in S?" can be answered
accurately. We allow the querying protocol to consider two
probes, and our goal is to optimize the size of the array needed
to store small subsets. We shall first look at some results that
are known, and then later consider the special case of storing
3-element subsets of U in which case we have an asymptotically
tight answer for the order of the array size.