Polynomial-time Bernoulli group testing at the information threshold
Fix $\theta \in (0,1)$ and $\varepsilon > 0$, and let $k = \lfloor n^\theta \rfloor$. An unknown infected set $S \subseteq \{1, \dots, n\}$ is chosen uniformly among the sets of size $k$. Independently, a test matrix $X \in \{0,1\}^{N \times n}$ has independent entries equal to $1$ with probability $q$, where $$q = 1 - 2^{-1/k}, \qquad N = \left\lceil (1+\varepsilon) \log_2 \binom{n}{k} \right\rceil,$$ so that each test is positive with probability $1/2$. The outcome of test $a$ is the noiseless $Y_a = \mathbf{1}\{X_{ai} = 1 \text{ for some } i \in S\}$. No design whatever allows approximate recovery of $S$ with $(1 - \varepsilon) \log_2 \binom{n}{k}$ tests, and with this design an exhaustive search over sets of size $k$ recovers all but $o(k)$ elements of $S$ with probability tending to one. Scarlett and Cevher's separate decoding of items runs in polynomial time and needs a factor $1/\ln 2$ more tests. Coja-Oghlan, Gebhard, Hahn-Klimroth, Wein and Zadik proved that low-degree polynomials fail in a detection version of the problem below an explicit number of tests, which exceeds $\log_2 \binom{n}{k}$ when $\theta$ is small and tends to $\log_2 \binom{n}{k} / \ln 2$ as $\theta \to 0$, and Lovig and Zadik proved that a natural class of low-temperature local Markov chain Monte Carlo methods takes super-polynomial time when $\theta$ is small and $N \le 1.4749 \log_2 \binom{n}{k}$.
Problem. For every fixed $\theta$ and $\varepsilon$ as above, is there a decoder, possibly randomized, with running time polynomial in $n$, which receives $(X, Y, k)$ and returns a set $\widehat S$ of size $k$ such that $|\widehat S \,\triangle\, S| / k \to 0$ in probability as $n \to \infty$? The probability is over the infected set, the test matrix and the decoder's randomness; the polynomial and the algorithm may depend on $\theta$ and $\varepsilon$; and the design is prescribed, so the decoder cannot replace it by another pooling scheme.
Source: Iliopoulos and Zadik (2021), who ask whether non-adaptive Bernoulli group testing has a computational-statistical gap for approximate recovery, after Aldridge, Johnson and Scarlett (2019), Open Problem 3; posed again by Lovig and Zadik (2026) and in the second edition of Aldridge, Johnson and Scarlett (2026), section on computational considerations. Stated in this form by AIM — Open Applied Problems.
Imported from github.com/MColbrook/AIM.
Classification
- Primary
- ST — Statistics Theory
- Secondary
- IT, PR
- Keywords
- AIM Open Applied Problems, computational-statistical gaps, group testing
References
@inproceedings{iliopoulos2021,
author = {Iliopoulos, Fotis and Zadik, Ilias},
title = {Group testing and local search: is there a computational-statistical gap?},
booktitle = {Proceedings of Thirty Fourth Conference on Learning Theory},
series = {Proceedings of Machine Learning Research},
volume = {134},
publisher = {PMLR},
year = {2021},
pages = {2499--2551},
url = {https://proceedings.mlr.press/v134/iliopoulos21a.html},
eprint = {2011.05258},
archivePrefix = {arXiv},
}
@article{aldridge2019,
author = {Aldridge, Matthew and Johnson, Oliver and Scarlett, Jonathan},
title = {Group testing: an information theory perspective},
journal = {Found. Trends Commun. Inf. Theory},
volume = {15},
number = {3--4},
year = {2019},
pages = {196--392},
doi = {10.1561/0100000099},
}
@article{aldridge2026,
author = {Aldridge, Matthew and Johnson, Oliver and Scarlett, Jonathan},
title = {Group testing: an information theory perspective},
journal = {Found. Trends Commun. Inf. Theory},
volume = {23},
number = {1--2},
year = {2026},
pages = {1--221},
doi = {10.1108/FTCIT-11-2025-0150},
eprint = {1902.06002},
archivePrefix = {arXiv},
note = {Second edition},
}
@article{lovig2026,
author = {Lovig, Max and Zadik, Ilias},
title = {On the {MCMC} performance in {B}ernoulli group testing and the random max-set cover problem},
journal = {Ann. Appl. Probab.},
volume = {36},
number = {3},
year = {2026},
pages = {2626--2679},
doi = {10.1214/25-AAP2290},
eprint = {2410.09231},
archivePrefix = {arXiv},
}
@inproceedings{cojaoghlan2022,
author = {Coja-Oghlan, Amin and Gebhard, Oliver and Hahn-Klimroth, Max and Wein, Alexander S. and Zadik, Ilias},
title = {Statistical and computational phase transitions in group testing},
booktitle = {Proceedings of Thirty Fifth Conference on Learning Theory},
series = {Proceedings of Machine Learning Research},
volume = {178},
publisher = {PMLR},
year = {2022},
pages = {4764--4781},
url = {https://proceedings.mlr.press/v178/coja-oghlan22a.html},
eprint = {2206.07640},
archivePrefix = {arXiv},
}
@article{scarlett2018,
author = {Scarlett, Jonathan and Cevher, Volkan},
title = {Near-optimal noisy group testing via separate decoding of items},
journal = {IEEE J. Sel. Top. Signal Process.},
volume = {12},
number = {5},
year = {2018},
pages = {902--915},
doi = {10.1109/JSTSP.2018.2844818},
eprint = {1710.08704},
archivePrefix = {arXiv},
}
@misc{aim-bernoulli-group-testing,
author = {Brunton, Steve and Colbrook, Matthew J. and de Hoop, Maarten V. and Stepaniants, George and Townsend, Alex and Ward, Rachel},
title = {{Polynomial-time Bernoulli group testing at the information threshold}},
howpublished = {AIM --- Open Applied Problems, GitHub repository},
year = {2026},
url = {https://github.com/MColbrook/AIM/blob/a153f469ee0ea64e876b2ad97c79d252c19a3e22/problems/552-bernoulli-group-testing.md},
note = {Entry 552 at commit a153f46, 2026-10-13},
}
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00276, "Polynomial-time Bernoulli group testing at the information threshold", clopen.solutions.