Certified exact bounds for adaptive quantitative group testing with two defectives
Abstract
We determine the maximum population size for which exactly two defective items can always be identified using at most k adaptive quantitative tests, for every 0≤ k≤10. Each test reports the number of defectives in a chosen subset. The exact maxima for eight, nine and ten tests are 65, 112 and 192, respectively. We also classify all pairs of sizes of two disjoint sets, each containing exactly one defective, that can be resolved within each test budget through eight. These exact results are supported by explicit strategies and maximality certificates checked by programs separate from the search implementation. Additional results include partial nine-test boundaries and an eleven-test strategy for 328 items; maximality of the latter remains open.
Related
- Tight Bounds for Equivalence Testing with Non-Adaptive Conditional Samples
- Optimal Certified Multiple Testing with E-values
- Certified bounds on optimization problems in quantum theory
- Certified Per-Instance Unlearning Using Individual Sensitivity Bounds
- Pay Only for Disagreement: Certified No-Regression Verdicts for Model Updates with Matching Label-Complexity Bounds
BibTeX
@misc{karpelevitch2026certified,
title = {{Certified exact bounds for adaptive quantitative group testing with two defectives}},
author = {Fedor Karpelevitch},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.38489},
eprint = {2609.38489},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.38489},
}
RIS
TY - UNPB
TI - Certified exact bounds for adaptive quantitative group testing with two defectives
AU - Fedor Karpelevitch
PY - 2026
DA - 2026/09/29
PB - arXiv
DO - 10.48550/arxiv.2609.38489
UR - https://arxiv.org/abs/2609.38489
AB - We determine the maximum population size for which exactly two defective items can always be identified using at most k adaptive quantitative tests, for every 0≤ k≤10. Each test reports the number of defectives in a chosen subset. The exact maxima for eight, nine and ten tests are 65, 112 and 192, respectively. We also classify all pairs of sizes of two disjoint sets, each containing exactly one defective, that can be resolved within each test budget through eight. These exact results are supported by explicit strategies and maximality certificates checked by programs separate from the search implementation. Additional results include partial nine-test boundaries and an eleven-test strategy for 328 items; maximality of the latter remains open.
ER -