论文标题
具有运行长度约束的小组测试的可实现率和算法
Achievable Rates and Algorithms for Group Testing with Runlength Constraints
论文作者
论文摘要
在本文中，我们研究了$（k，n，d）$ - 叠加的代码的最小长度的界限。 [1]，在具有运行长度约束的非自适应组测试算法的背景下。 a $（k，n，d）$ - 长度$ t $的叠加代码是a $ t \ times n $二进制矩阵，每列中的任何两个1均以至少$ d $ 0的运行方式分开，因此，对于任何列$ \ mathbf {c} $ and $ k-k-1 $ $ k-1 $ $ k-ymath us $ k-k-1列有$ 0 $。 Agarwal等。证明存在$ t =θ的存在（dk \ log（n/k）+k^2 \ log（n/k））$。在这里，我们更多地详细研究了这两个主要术语面前的系数以及较低术语的作用。我们表明，通过使用不同的结构以及在这种情况下对Lovász本地引理的适当利用，可以通过[1]中的构造获得改进。我们的发现还建议$ o（n^k）$随机的拉斯维加斯算法用于构建此类代码。我们还将结果扩展到具有运行长度约束的两阶段组测试算法。
In this paper, we study bounds on the minimum length of $(k,n,d)$-superimposed codes introduced by Agarwal et al. [1], in the context of Non-Adaptive Group Testing algorithms with runlength constraints. A $(k,n,d)$-superimposed code of length $t$ is a $t \times n$ binary matrix such that any two 1's in each column are separated by a run of at least $d$ 0's, and such that for any column $\mathbf{c}$ and any other $k-1$ columns, there exists a row where $\mathbf{c}$ has $1$ and all the remaining $k-1$ columns have $0$. Agarwal et al. proved the existence of such codes with $t=Θ(dk\log(n/k)+k^2\log(n/k))$. Here we investigate more in detail the coefficients in front of these two main terms as well as the role of lower order terms. We show that improvements can be obtained over the construction in [1] by using different constructions and by an appropriate exploitation of the Lovász Local Lemma in this context. Our findings also suggest $O(n^k)$ randomized Las Vegas algorithms for the construction of such codes. We also extend our results to Two-Stage Group Testing algorithms with runlength constraints.
