On the MCMC performance in Bernoulli group testing and the random max-set cover problem
Maxwell Lovig, Ilias Zadik · The Annals of Applied Probability · 2026
The group testing problem is a canonical inference task where one seeks to identify k infected individuals out of a population of n people, based on the outcomes of N group tests. Of particular interest is the case of Bernoulli group testing (BGT), where each individual participates in each test independently and with a fixed probability. BGT is known to be “information-theoretically” optimal, as there exists a decoder that can approximately recover the set of infected individuals with high probability as n grows using N∗=log2( n k) BGT tests, which is the minimum required number of tests among all group testing designs. An important open question in the field is if a polynomial-time decoder exists for BGT which succeeds also with N∗ samples. In a recent paper (IZ’21) some evidence was presented (but no proof) that a simple low-temperature MCMC method could succeed. The evidence was based on a first-moment (or “annealed”) analysis of the landscape and simulations showing the MCMC success for n≈1,000s. In this work, we prove that, despite the intriguing success in simulations for small n, the proposed class of MCMC methods for BGT with N∗ samples takes super-polynomial-in-n time to identify the infected individuals. We show that the suggested first-moment picture by the previous work has been an artifact of “rare bad” events, and via a delicate conditional second-moment method we conclude that an overlap gap property takes place in BGT leading to bottlenecks for the MCMC methods. Towards obtaining our results, we establish the tight max-satisfiability thresholds of random k-set cover, a result of potentially independent interest in the study of random constraint satisfaction problems.