论文标题
改进了嘈杂组测试的界限，每项恒定测试
Improved bounds for noisy group testing with constant tests per item
论文作者
论文摘要
小组测试问题涉及识别大量人群中的一小部分受感染者。我们可以使用的是一个测试程序，使我们能够一起测试几个人。在理想化的环境中，仅当包括至少一个感染的人而否则为阴性时，测试是积极的。近年来，在这种嘈杂的环境中了解信息理论和算法属性方面取得了重大进展。在本文中，我们考虑了一个嘈杂的小组测试变体，其中测试结果以某些概率翻转，包括敏感性和特异性可以使用任意值的现实情况。使用测试设计，每个人都被分配给固定数量的测试，我们为两种通常考虑的推理算法提供了明确的算法界限，从而自然地扩展了Scarlett \＆Cevher（2016）和Scarlett \＆Johnson（2020）的结果。在这些嘈杂的小组测试模型中，我们为有效算法提供了提高的性能保证 - 的确，对于本文提供的大量参数选择，本文提供的界限是当前证明的最强的。
The group testing problem is concerned with identifying a small set of infected individuals in a large population. At our disposal is a testing procedure that allows us to test several individuals together. In an idealized setting, a test is positive if and only if at least one infected individual is included and negative otherwise. Significant progress was made in recent years towards understanding the information-theoretic and algorithmic properties in this noiseless setting. In this paper, we consider a noisy variant of group testing where test results are flipped with certain probability, including the realistic scenario where sensitivity and specificity can take arbitrary values. Using a test design where each individual is assigned to a fixed number of tests, we derive explicit algorithmic bounds for two commonly considered inference algorithms and thereby naturally extend the results of Scarlett \& Cevher (2016) and Scarlett \& Johnson (2020). We provide improved performance guarantees for the efficient algorithms in these noisy group testing models -- indeed, for a large set of parameter choices the bounds provided in the paper are the strongest currently proved.
