























In the adaptive bitprobe model answering membership queries in two bitprobes, we consider the class of restricted schemes as introduced by Kesh and Sharma (Discrete Applied Mathematics 2021). In that paper, the authors showed that such restricted schemes storing subsets of size 2 require $Ω(m^\frac{2}{3})$ space. In this paper, we generalise the result to arbitrary subsets of size $n$, and prove that the space required for such restricted schemes will be $Ω(\left(\frac{m}{n}\right)^{1 - \frac{1}{\lfloor n / 4 \rfloor + 2}})$.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。