论文标题
一般稀疏性制度中的最佳非自适应概率组测试
Optimal Non-Adaptive Probabilistic Group Testing in General Sparsity Regimes
论文作者
论文摘要
在本文中，我们考虑了无嘈杂的非自适应概率群体测试的问题，其中目标是有缺陷集的高概率恢复。 We show that in the case of $n$ items among which $k$ are defective, the smallest possible number of tests equals $\min\{ C_{k,n} k \log n, n\}$ up to lower-order asymptotic terms, where $C_{k,n}$ is a uniformly bounded constant (varying depending on the scaling of $k$ with respect to $n$) with a simple explicit 表达。算法上限是从对确定缺陷（DD）算法的现有分析进行的次要适应以及与算法无关的下限构建的，这是基于对制度的现有作品的$ k \ le n^{1-ω（1）}（1）} $和$ k =θ（n）$。在足够稀疏的制度（包括$ k = o \ big（\ frac {n} {\ log n} \ big）$）中，我们的主要结果通过避免避免假设$ k \ le n^^{1- {1- {1- {1-} $（neyeas），而$ k的coja-oghlan {\ em et al。}（2020）（2020） \ frac {n} {\ log n} \ big）$），我们的主要结果表明，对于任何非零目标成功概率，单个测试在任何非零目标成功概率上都是最佳的，因此就误差概率和假定的缩放量表而言，增强了Aldridge（2019）的现有结果。
In this paper, we consider the problem of noiseless non-adaptive probabilistic group testing, in which the goal is high-probability recovery of the defective set. We show that in the case of $n$ items among which $k$ are defective, the smallest possible number of tests equals $\min\{ C_{k,n} k \log n, n\}$ up to lower-order asymptotic terms, where $C_{k,n}$ is a uniformly bounded constant (varying depending on the scaling of $k$ with respect to $n$) with a simple explicit expression. The algorithmic upper bound follows from a minor adaptation of an existing analysis of the Definite Defectives (DD) algorithm, and the algorithm-independent lower bound builds on existing works for the regimes $k \le n^{1-Ω(1)}$ and $k = Θ(n)$. In sufficiently sparse regimes (including $k = o\big( \frac{n}{\log n} \big)$), our main result generalizes that of Coja-Oghlan {\em et al.} (2020) by avoiding the assumption $k \le n^{1-Ω(1)}$, whereas in sufficiently dense regimes (including $k = ω\big( \frac{n}{\log n} \big)$), our main result shows that individual testing is asymptotically optimal for any non-zero target success probability, thus strengthening an existing result of Aldridge (2019) in terms of both the error probability and the assumed scaling of $k$.
