BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/628
DTSTAMP:20230914T125932Z
SUMMARY:The Bit-Probe Complexity of Set Membership
DESCRIPTION:Speaker: Mohit Garg\n\nAbstract: \nAbstract: We will consider t
he fundamental trade-off between the compactness of information representa
tion and the efficiency of information extraction in the context of the se
t membership problem. In the set membership problem\, a set S of size at m
ost $n$ from a universe of size $m$ is to be represented as a short bit ve
ctor in order to answer membership queries of the form ``Is x in S?'' by p
robing 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. Impr
oving on the works of Buhrman\, Milterson\, Radhakrishnan and Venkatesh (2
002) and Alon and Feige (2009) we provide better bounds on $s(m\,n\,t)$ fo
r a range of $m$\, $n$ and $t$.\n\nFor two probes:\n\n$s(m\,n\,2) =O(m^{1-
\\frac{1}{4n+1}})$\; this improves on a result of Alon and Feige that st
ates that for $n \\leq \\lg m$\, $s(m\,n\,2) = O( m n \\lg ((\\lg m) / n)
/ \\lg m)$\n$s(m\,n\,2)= \\Omega(m^{1-\\frac{1}{\\lfloor n/4 \\rfloor}})$\
; in particular\, $s(m\,n\,2)=\\Omega(m)$ for $n \\geq 4\\lg m$.\n\nFor th
ree probes:\n\n$s(m\,n\,3) = \\tilde{O}(\\sqrt{mn}).$ This improves a resu
lt of Alon and Feige that states that $s(m\,n\,2)=O(m^{\\frac{2}{3}} n^{\\
frac{1}{3}})$. For $n\\approx \\lg m$\, our general lower bound implies
a lower bound of $\\Omega(\\sqrt{m})$ which comes close to the upper bound
.\nThe best non-adaptive schemes (when probes are made in parallel) for $t
\\geq 4$ use majority decoding to answer membership queries. For three non
-adaptive probes\, we show a lower bound for majority decoding schemes: $s
(m\,n\,t)=\\Omega(m^{1-\\frac 1{cn}})$ for some $c>0$. Lower bounds are
also obtained for other functions.\n\nIn general: We exhibit non-adaptive
and adaptive schemes for odd $t\\geq 5$ that use significantly less space
than the schemes of Buhrman et al. We also obtain slight improvement over
their general lower bound.\n\n(This is joint work with Jaikumar Radhakrish
nan.)\n
URL:https://www.tcs.tifr.res.in/web/events/628
DTSTART;TZID=Asia/Kolkata:20151008T143000
DTEND;TZID=Asia/Kolkata:20151008T153000
LOCATION:AG-80
END:VEVENT
END:VCALENDAR