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
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
(Joint work with Jaikumar Radhakrishnan)