Statistical Physics of Group Testing

Abstract

This paper provides a short introduction to the group testing problem, and reviews various aspects of its statistical physics formulation. Two main issues are discussed: the optimal design of pools used in a two-stage testing experiment, like the one often used in medical or biological applications, and the inference problem of detecting defective items based on pool diagnosis. The paper is largely based on: M. Mézard and C. Toninelli, arXiv:0706.3104, and M. Mézard and M. Tarzia {\it Phys. Rev. E} {\bf 76}, 041124 (2007).

12 pages, 5 figures. To appear in proceedings of Conference "IW-SMI 2007" (Kyoto, september 2007)

References in corpus (9)

• The Bethe lattice spin glass revisited
• The random K-satisfiability problem: from an analytic solution to an efficient algorithm
• The number of guards needed by a museum: A phase transition in vertex covering of random graphs
• Core percolation in random graphs: a critical phenomena analysis
• Minimal vertex covers on finite-connectivity random graphs - a hard-sphere lattice-gas picture
• Vertex cover problem studied by cavity method: Analytics and population dynamics
• Message passing for vertex covers
• Long Range Frustrations in a Spin Glass Model of the Vertex Cover Problem
• Statistical Mechanics of the Hyper Vertex Cover Problem

Cited by in corpus (2)

• Active pooling design in group testing based on Bayesian posterior prediction
• Bayesian inference of infected patients in group testing with prevalence estimation