Tata Institute of Fundamental Research
The Bit-Probe Complexity of Set Membership
PhD Synopsis Seminar
Speaker:
Mohit Garg
Organiser:
Kavitha Telikepalli
Date:
Thursday, 8 Oct 2015, 14:30 to 15:30
Venue:
AG-80
(Scan to add to calendar)
Abstract:
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 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$.
For two probes:
$s(m,n,2) =O(m^{1-\frac{1}{4n+1}})$; this improves on a result of Alon and Feige that states that for $n \leq \lg m$, $s(m,n,2) = O( m n \lg ((\lg m) / n) / \lg m)$
$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$.
For three probes:
$s(m,n,3) = \tilde{O}(\sqrt{mn}).$ This improves a result 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.
The 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.
In 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.
(This is joint work with Jaikumar Radhakrishnan.)
| Speaker: | Mohit Garg |
| Organiser: | Kavitha Telikepalli |
| Date: | Thursday, 8 Oct 2015, 14:30 to 15:30 |
| Venue: | AG-80 |
(Scan to add to calendar)
Abstract:
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 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$.
For two probes:
$s(m,n,2) =O(m^{1-\frac{1}{4n+1}})$; this improves on a result of Alon and Feige that states that for $n \leq \lg m$, $s(m,n,2) = O( m n \lg ((\lg m) / n) / \lg m)$
$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$.
For three probes:
$s(m,n,3) = \tilde{O}(\sqrt{mn}).$ This improves a result 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.
The 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.
In 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.
(This is joint work with Jaikumar Radhakrishnan.)
For two probes:
$s(m,n,2) =O(m^{1-\frac{1}{4n+1}})$; this improves on a result of Alon and Feige that states that for $n \leq \lg m$, $s(m,n,2) = O( m n \lg ((\lg m) / n) / \lg m)$
$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$.
For three probes:
$s(m,n,3) = \tilde{O}(\sqrt{mn}).$ This improves a result 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.
The 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.
In 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.
(This is joint work with Jaikumar Radhakrishnan.)