论文标题
在两种自适应BITPROBE模型中的限制方案的下限
Lower Bounds for Restricted Schemes in the Two-Adaptive Bitprobe Model
论文作者
论文摘要
在两个Bitprobes中回答成员查询的自适应BITPROBE模型中，我们考虑了Kesh和Sharma介绍的限制方案类别（离散应用数学2021）。在该论文中，作者表明，存储大小2的子集的这种限制方案需要$ω（m^\ frac {2} {3} {3}）$ space。在本文中，我们将结果概括为尺寸$ n $的任意子集，并证明此类限制方案所需的空间为$ω（\ left（\ frac {m} {m} {n} {n} \ right）^{1 - \ frac {1} {\ lfloor n / 4 \ n / 4 \ rfloor + 2}}）$。
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}})$.
