English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

In this work we study the fundamental limits of approximate recovery in thecontext of group testing. One of the most well-known, theoretically optimal,and easy to implement testing procedures is the non-adaptive Bernoulli grouptesting problem, where all tests are conducted in parallel, and each item ischosen to be part of any certain test independently with some fixedprobability. In this setting, there is an observed gap between the number oftests above which recovery is information theoretically (IT) possible, and thenumber of tests required by the currently best known efficient algorithms tosucceed. Often times such gaps are explained by a phase transition in thelandscape of the solution space of the problem (an Overlap Gap Property phasetransition).  In this paper we seek to understand whether such a phenomenon takes place forBernoulli group testing as well. Our main contributions are the following: (1)We provide first moment evidence that, perhaps surprisingly, such a phasetransition does not take place throughout the regime for which recovery is ITpossible. This fact suggests that the model is in fact amenable to local searchalgorithms ; (2) we prove the complete absence of "bad" local minima for a partof the "hard" regime, a fact which implies an improvement over knowntheoretical results on the performance of efficient algorithms for approximaterecovery without false-negatives, and finally (3) we present extensivesimulations that strongly suggest that a very simple local algorithm known asGlauber Dynamics does indeed succeed, and can be used to efficiently implementthe well-known (theoretically optimal) Smallest Satisfying Set (SSS) estimator.

Group testing and local search: is there a computational-statistical gap?