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.