论文标题
小组测试和本地搜索：是否存在计算统计差距？
Group testing and local search: is there a computational-statistical gap?
论文作者
论文摘要
在这项工作中，我们研究了小组测试背景下近似恢复的基本限制。最著名的，理论上最佳且易于实现的测试程序之一是非自适应的Bernoulli组测试问题，其中所有测试均在同时进行，并且每个项目都被选为具有某些固定概率的独立测试的一部分。在这种情况下，观察到的测试次数在理论上是可能的（IT）信息与当前最知名的有效算法成功的测试数量之间的差异。通常，这种差距是通过问题解决方案空间的景观中的相变（重叠间隙属性相变）来解释的。 在本文中，我们试图了解伯努利小组测试是否发生这种现象。我们的主要贡献是：（1）我们提供的第一刻证据表明，令人惊讶的是，在整个恢复过程中，这种相转换不会发生。这个事实表明，该模型实际上适合本地搜索算法； (2) we prove the complete absence of "bad" local minima for a part of the "hard" regime, a fact which implies an improvement over known theoretical results on the performance of efficient algorithms for approximate recovery without false-negatives, and finally (3) we present extensive simulations that strongly suggest that a very simple local algorithm known as Glauber Dynamics does indeed succeed, and can be used to efficiently implement the well-known （理论上最佳）最小的满足集（SSS）估计器。
In this work we study the fundamental limits of approximate recovery in the context of group testing. One of the most well-known, theoretically optimal, and easy to implement testing procedures is the non-adaptive Bernoulli group testing problem, where all tests are conducted in parallel, and each item is chosen to be part of any certain test independently with some fixed probability. In this setting, there is an observed gap between the number of tests above which recovery is information theoretically (IT) possible, and the number of tests required by the currently best known efficient algorithms to succeed. Often times such gaps are explained by a phase transition in the landscape of the solution space of the problem (an Overlap Gap Property phase transition). In this paper we seek to understand whether such a phenomenon takes place for Bernoulli group testing as well. Our main contributions are the following: (1) We provide first moment evidence that, perhaps surprisingly, such a phase transition does not take place throughout the regime for which recovery is IT possible. This fact suggests that the model is in fact amenable to local search algorithms ; (2) we prove the complete absence of "bad" local minima for a part of the "hard" regime, a fact which implies an improvement over known theoretical results on the performance of efficient algorithms for approximate recovery without false-negatives, and finally (3) we present extensive simulations that strongly suggest that a very simple local algorithm known as Glauber Dynamics does indeed succeed, and can be used to efficiently implement the well-known (theoretically optimal) Smallest Satisfying Set (SSS) estimator.
