Year: 2016 10/5 [elc]   ELC C01 seminar (Dr. Mohit Garg) Place : Ookayama Campus＠TITECH, W8E-10F seminar room 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) 

horiyama@al.ics.saitama-u.ac.jp