ELC C01 seminar (Dr. Mohit Garg)

I am pleased to announce that we will have a new PD fellow
Dr. Mohit Garg from Tata Inst. of Fundamental Research as a
member of C01 and jointly A01.  He wil give the following talk
at Ookayama campus.  Even if you cannot attend this seminar,
please stop by at the ELC office to chat with him.

Host: Osamu Watanabe

 Date: Oct. 5th, 2016
 Time: 16:40 - 17:40
 Place: Tokyo Inst. of Tech, Ookayama Campus, W8E-10F seminar room

 Speaker: Mohit Garg
 Title: Set membership with non-adaptive bit-probes

 Abstract: 
 We will consider the fundamental trade-off between the
 compactness of information representation and the efficiency of
 information extraction in the context of the set membership problem.
 In the set membership problem, a set S of size at most n from a
 universe of size m is to be represented as a short bit vector in
 order to answer membership queries of the form "Is x in S?'' by
 (non-adaptively) probing the bit vector at t places. The bit-probe
 complexity s(m,n,t)  is the minimum number of bits of storage needed
 for such a scheme. Improving on the works of Buhrman, Milterson,
 Radhakrishnan and Venkatesh (2002) and Alon and Feige (2009) we
 provide better bounds on s(m,n,t) for a range of m, n and t.

 In this talk, we will see the existence of non-adaptive schemes for
 odd t > = 5 that use O(m^(2/(t-1)) n^(1-2/(t-1))lg (2m)/n) space and
 the membership queries are answered by applying the Majority
 function to the t bits probed.

 In the case of t=3 probes,  we will see that Majority does not help;
 all schemes that use Majority for answering membership queries and
 can represent large sets (n>= lg m) must use \Omega(m) space (a task
 that can be accomplished by just a single bit probe using the
 characteristic vector representation). In fact, this is true not just
 for Majority but also for most three variable boolean functions.
 However, for two types of functions, the lower bound that is obtained
 is \Omega(\sqrt(mn)).

 (Joint work with Jaikumar Radhakrishnan)