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