Summary: We consider the bit-probe complexity of the set membership problem: represent an \(n\)-element subset \(S\) of an \(m\)-element universe as a succinct bit vector so that membership queries of the form “Is \(x\in S\)” can be answered using at most \(t\) probes into the bit vector. Let \(s(m,n,t)\) (resp. \(s_N(m,n,t)\)) denote the minimum number of bits of storage needed when the probes are adaptive (resp. non-adaptive). M. Lewenstein et al. [Lect. Notes Comput. Sci. 8737, 630–641 (2014; Zbl 1425.68090)] obtain fully-explicit schemes that show that \[s(m,n,t)= \mathcal{O}((2^t-1)m^{1/(t-\min\{2\lfloor\log n\rfloor, n-3/2\})})\] for \(n=2\), \(t\ge\lfloor\log n\rfloor+1\).
In this work, we improve this bound when the probes are allowed to be superlinear in \(n\), i.e., when \(t\ge\Omega(n\log n)\), \(n\ge 2\), we design fully-explicit schemes that show that \[s(m,n,t)=\mathcal{O}((2^t-1)m^{1/(t-\frac{n-1}{2^{t/(2(n-1))}})}),\] asymptotically (in the exponent of \(m\)) close to the non-explicit upper bound on \(s(m,n,t)\) derived by J. Radhakrishnan et al. [Lect. Notes Comput. Sci. 6347, 159–170 (2010; Zbl 1287.68031)], for constant \(n\). In the non-adaptive setting, it was shown by M. Garg and J. Radhakrishnan [LIPIcs – Leibniz Int. Proc. Inform. 66, Article 38, 13 p. (2017; Zbl 1402.68034)] that for a large constant \(n_0\), for \(n\ge n_0\), \(s_N(m,n,3)= \sqrt{mn}\). We improve this result by showing that the same lower bound holds even for storing sets of size \(2\), i.e., \(s_N(m,2,3)\ge\Omega(\sqrt{m})\).
For the entire collection see [Zbl 1445.68013].