Group Testing with Random Pools: optimal two-stage algorithms
| dc.creator | Mezard, Marc | |
| dc.creator | Toninelli, Cristina | |
| dc.date | 2007-06-21 | |
| dc.date.accessioned | 2026-07-07T08:42:30Z | |
| dc.date.available | 2026-07-07T08:42:30Z | |
| dc.description | We study Probabilistic Group Testing of a set of N items each of which is defective with probability p. We focus on the double limit of small defect probability, p<<1, and large number of variables, N>>1, taking either p->0 after $N\to\infty$ or $p=1/N^β$ with $β\in(0,1/2)$. In both settings the optimal number of tests which are required to identify with certainty the defectives via a two-stage procedure, $\bar T(N,p)$, is known to scale as $Np|\log p|$. Here we determine the sharp asymptotic value of $\bar T(N,p)/(Np|\log p|)$ and construct a class of two-stage algorithms over which this optimal value is attained. This is done by choosing a proper bipartite regular graph (of tests and variable nodes) for the first stage of the detection. Furthermore we prove that this optimal value is also attained on average over a random bipartite graph where all variables have the same degree, while the tests have Poisson-distributed degrees. Finally, we improve the existing upper and lower bound for the optimal number of tests in the case $p=1/N^β$ with $β\in[1/2,1)$. | |
| dc.description | 12 pages | |
| dc.identifier | https://arxiv.org/abs/0706.3104 | |
| dc.identifier | http://arxiv.org/abs/0706.3104 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/141980 | |
| dc.subject | Data Structures and Algorithms | |
| dc.subject | Disordered Systems and Neural Networks | |
| dc.subject | Statistical Mechanics | |
| dc.subject | Information Theory | |
| dc.title | Group Testing with Random Pools: optimal two-stage algorithms | |
| dc.type | text |