Seminar at SMU 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.