Optimal Non-Adaptive Group Testing with One-Sided Error Guarantees

Daniel McMorrow; Jonathan Scarlett

arxiv: 2506.10374 · v4 · submitted 2025-06-12 · 💻 cs.IT · math.IT· math.ST· stat.TH

Optimal Non-Adaptive Group Testing with One-Sided Error Guarantees

Daniel McMorrow , Jonathan Scarlett This is my paper

Pith reviewed 2026-05-19 10:15 UTC · model grok-4.3

classification 💻 cs.IT math.ITmath.STstat.TH

keywords group testingapproximate recoveryone-sided errornon-adaptiveinformation theoretic boundssparse defectives

0 comments

The pith

An algorithm matches the optimal threshold for approximate group testing when allowing only false negatives.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper examines non-adaptive group testing for identifying a sparse set of defective items through pooled tests whose outcomes indicate the presence of at least one defective. It focuses on approximate recovery that tolerates a small number of errors but restricts those errors to one side only. For the false-negative-only case, which requires outputting a subset of the true defectives, the work establishes that an algorithm attains the same information-theoretic threshold previously known for the standard two-sided error setting. For the false-positive-only case, which requires outputting a superset containing all defectives, a converse argument shows that the stronger of two known algorithms already achieves the best possible rate. These distinctions matter because applications often penalize one direction of error far more than the other.

Core claim

In the non-adaptive approximate group testing problem, there exists an algorithm matching the optimal threshold of two-sided approximate recovery under false negatives only, i.e., when the goal is to output a subset of the defectives. Under false positives only, i.e., when the goal is to output a superset of the defectives, a converse bound shows that the better of two existing algorithms is optimal.

What carries the argument

Information-theoretic threshold analysis for one-sided approximate recovery in the standard model of k defectives among n items with non-adaptive test matrices.

If this is right

Recovery procedures can attain the best known rate while guaranteeing that every reported defective is truly defective.
Current algorithms for superset recovery already saturate the information-theoretic limit and cannot be improved in rate.
The thresholds apply in the asymptotic regime where n grows large and k scales as a function of n.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

Applications that cannot tolerate false alarms may prefer the subset-recovery algorithm since it matches the rate of more permissive two-sided methods.
The same one-sided threshold analysis could be applied to related sparse-recovery tasks such as pooled screening in biology.
Whether adaptive testing yields further gains under these one-sided criteria remains open.

Load-bearing premise

The standard model holds in which exactly k items are defective among n total items and all tests are chosen in advance without adaptation.

What would settle it

A construction or simulation demonstrating that no algorithm succeeds with high probability at the claimed rate for the false-negative-only recovery criterion at large n would disprove the existence result.

Figures

Figures reproduced from arXiv: 2506.10374 by Daniel McMorrow, Jonathan Scarlett.

read the original abstract

The group testing problem consists of determining a sparse subset of defective items from within a larger set of items via a series of tests, where each test outcome indicates whether at least one defective item is included in the test. We study the approximate recovery setting, where the recovery criterion of the defective set is relaxed to allow a small number of items to be misclassified. In particular, we consider one-sided approximate recovery criteria, where we allow either only false negative or only false positive misclassifications. Under false negatives only (i.e., finding a subset of defectives), we show that there exists an algorithm matching the optimal threshold of two-sided approximate recovery. Under false positives only (i.e., finding a superset of the defectives), we provide a converse bound showing that the better of two existing algorithms is optimal.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

This paper matches the two-sided approximate recovery threshold for false-negative-only recovery and proves a converse showing existing algorithms are optimal for false-positive-only recovery in non-adaptive group testing.

read the letter

Hi there, the main thing to know is that this work separates the one-sided error cases in approximate non-adaptive group testing and pins down the thresholds cleanly. For recovering a subset of the defectives (false negatives only), they give an algorithm that hits the same asymptotic rate as the best two-sided approximate recovery results. For recovering a superset (false positives only), they add a converse that shows the better of the two prior algorithms cannot be improved upon. This distinction is the core advance, and it comes from adapting standard matrix constructions and information-theoretic counting arguments rather than new machinery. The paper handles the usual sparse defectives model with k out of n items and stays within the non-adaptive testing framework, which keeps the claims grounded. What it does well is make the error directions explicit and show where the difficulty shifts: false negatives appear easier to tolerate at the information limit, while false positives hit a tighter wall. The arguments line up with existing benchmarks in the literature without circularity or hidden fitting. On the softer side, everything stays asymptotic and existence-oriented, so there is little on finite-length performance, explicit constructions that run fast, or how the approximation parameter behaves outside the large-n regime. That is not a flaw for a theory paper, but it does mean follow-up work would be needed before these bounds directly inform moderate-sized testing protocols. This is aimed at people already working in combinatorial algorithms and information theory for group testing. A reader who cares about refining error tolerances in pooled testing or search problems will get concrete value from the threshold separations. The claims look defensible and the extension is non-routine enough that the paper deserves a serious referee rather than a desk reject.

Referee Report

0 major / 2 minor

Summary. The manuscript studies non-adaptive group testing under the sparse defective model (k defectives out of n items) in the approximate recovery regime with one-sided error guarantees. For false-negatives-only recovery (outputting a subset of the defectives), it claims an algorithm achieving the information-theoretic threshold previously known to be optimal for two-sided approximate recovery. For false-positives-only recovery (outputting a superset of the defectives), it provides a converse bound establishing optimality of the better of two existing algorithms.

Significance. If the central claims hold, the work supplies tight characterizations of the one-sided approximate recovery thresholds, extending standard information-theoretic arguments from the two-sided setting. The matching of the two-sided threshold under false negatives only is a notable positive result, while the converse for false positives clarifies the optimality status of prior constructions. These findings are relevant for applications preferring asymmetric error tolerances and rest on conventional combinatorial and information-theoretic tools against external benchmarks.

minor comments (2)

[Abstract] Abstract: the phrase 'matching the optimal threshold of two-sided approximate recovery' would be clearer if the explicit threshold expression (in terms of n and k) were stated or referenced to a specific equation in the main text.
The manuscript would benefit from an explicit comparison table or section summarizing the achieved rates versus the two existing algorithms mentioned for the false-positive case.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their careful reading of the manuscript and for the positive evaluation, including the recommendation for minor revision. The referee's summary accurately reflects the contributions regarding one-sided approximate recovery thresholds in non-adaptive group testing.

Circularity Check

0 steps flagged

No significant circularity in derivation chain

full rationale

The paper extends standard information-theoretic thresholds from two-sided approximate group testing to one-sided error settings using the sparse defective model (k out of n) and non-adaptive matrix constructions. The existence result matching the known two-sided threshold under false negatives only, and the converse establishing optimality for false positives only, rely on external combinatorial benchmarks and information-theoretic arguments rather than reducing to fitted parameters, self-definitional loops, or load-bearing self-citations. No equations or claims in the abstract or described structure exhibit the specific reductions required for circularity flags; the central claims retain independent content grounded outside the present work.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Results rest on standard group testing assumptions such as the combinatorial testing matrix and asymptotic regime for n and k; no new free parameters or invented entities are introduced in the abstract.

axioms (1)

domain assumption Standard sparse defectives model with k << n and non-adaptive test design
Invoked to define the recovery criteria and thresholds in the abstract.

pith-pipeline@v0.9.0 · 5668 in / 1128 out tokens · 38490 ms · 2026-05-19T10:15:27.712786+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

32 extracted references · 32 canonical work pages

[1]

The detection of defective members of large populations,

R. Dorfman, “The detection of defective members of large populations,” The Annals of Mathematical Statistics , vol. 14, no. 4, pp. 436–440, 1943

work page 1943
[2]

Pooling DNA in the identification of parents,

R. N. Curnow and A. P. Morris, “Pooling DNA in the identification of parents,” Heredity, vol. 80, no. 1, pp. 101–109, 1998

work page 1998
[3]

A pooling strategy for heterozygote screening of the ΔF508 cystic fibrosis mutation,

C. Gille, K. Grade, and C. Coutelle, “A pooling strategy for heterozygote screening of the ΔF508 cystic fibrosis mutation,” Human Genetics, vol. 86, pp. 289–291, 1991

work page 1991
[4]

An adaptive technique for local distribution,

J. Hayes, “An adaptive technique for local distribution,” IEEE Transactions on Communications , vol. 26, no. 8, pp. 1178–1186, 1978

work page 1978
[5]

Born again group testing: Multiaccess communications,

J. Wolf, “Born again group testing: Multiaccess communications,” IEEE Transactions on Information Theory , vol. 31, no. 2, pp. 185–191, 1985

work page 1985
[6]

Exact rule learning via boolean compressed sensing,

D. Malioutov and K. Varshney, “Exact rule learning via boolean compressed sensing,” in International Conference on Machine Learning . PMLR, 2013, pp. 765–773

work page 2013
[7]

What’s hot and what’s not: Tracking most frequent items dynamically,

G. Cormode and S. Muthukrishnan, “What’s hot and what’s not: Tracking most frequent items dynamically,” ACM Transactions on Database Systems (TODS), vol. 30, no. 1, pp. 249–278, 2005

work page 2005
[8]

Group testing: An information theory perspective,

M. Aldridge, O. Johnson, and J. Scarlett, “Group testing: An information theory perspective,” Foundations and Trends® in Communications and Information Theory , vol. 15, no. 3-4, pp. 196–392, 2019

work page 2019
[9]

Bounds on the length of disjunctive codes

A. D’yachkov and V . Rykov, “Bounds on the length of disjunctive codes.” Problems of Information Transmission, vol. 18, no. 3, pp. 166–171, 1983

work page 1983
[10]

Noise-resilient group testing: Limitations and constructions,

M. Cheraghchi, “Noise-resilient group testing: Limitations and constructions,” Discrete Applied Mathematics , vol. 161, no. 1-2, pp. 81–95, 2013

work page 2013
[11]

How little does non-exact recovery help in group testing?

J. Scarlett and V . Cevher, “How little does non-exact recovery help in group testing?” in IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP) , 2017, pp. 6090–6094

work page 2017
[12]

On the all-or-nothing behavior of Bernoulli group testing,

L. V . Truong, M. Aldridge, and J. Scarlett, “On the all-or-nothing behavior of Bernoulli group testing,” IEEE Journal on Selected Areas in Information Theory, vol. 1, no. 3, pp. 669–680, 2020

work page 2020
[13]

The capacity of adaptive group testing,

L. Baldassini, O. Johnson, and M. Aldridge, “The capacity of adaptive group testing,” in IEEE International Symposium on Information Theory , 2013, pp. 2676–2680

work page 2013
[14]

Non-adaptive probabilistic group testing with noisy measurements: Near-optimal bounds with efficient algorithms,

C. L. Chan, P. H. Che, S. Jaggi, and V . Saligrama, “Non-adaptive probabilistic group testing with noisy measurements: Near-optimal bounds with efficient algorithms,” in Allerton Conference on Communication, Control, and Computing , 2011, pp. 1832–1839

work page 2011
[15]

A method for detecting all defective members in a population by group testing,

F. K. Hwang, “A method for detecting all defective members in a population by group testing,” Journal of the American Statistical Association , vol. 67, no. 339, pp. 605–608, 1972

work page 1972
[16]

Optimal group testing,

A. Coja-Oghlan, O. Gebhard, M. Hahn-Klimroth, and P. Loick, “Optimal group testing,” in Conference on Learning Theory . PMLR, 2020, pp. 1374–1388

work page 2020
[17]

Information-theoretic and algorithmic thresholds for group testing,

——, “Information-theoretic and algorithmic thresholds for group testing,” IEEE Transactions on Information Theory , vol. 66, no. 12, pp. 7911–7928, 2020

work page 2020
[18]

Phase transitions in group testing,

J. Scarlett and V . Cevher, “Phase transitions in group testing,” in ACM-SIAM Symposium on Discrete Algorithms , 2016, pp. 40–53. 25

work page 2016
[19]

Performance of group testing algorithms with near-constant tests per item,

O. Johnson, M. Aldridge, and J. Scarlett, “Performance of group testing algorithms with near-constant tests per item,” IEEE Transactions on Information Theory, vol. 65, no. 2, pp. 707–723, 2018

work page 2018
[20]

Pooled testing to isolate infected individuals,

M. Aldridge, “Pooled testing to isolate infected individuals,” in Annual Conference on Information Sciences and Systems (CISS) . IEEE, 2021, pp. 1–5

work page 2021
[21]

SAFFRON: A fast, efficient, and robust framework for group testing based on sparse-graph codes,

K. Lee, K. Chandrasekher, R. Pedarsani, and K. Ramchandran, “SAFFRON: A fast, efficient, and robust framework for group testing based on sparse-graph codes,” IEEE Transactions on Signal Processing , vol. 67, no. 17, pp. 4649–4664, 2019

work page 2019
[22]

On finding a subset of non-defective items from a large population,

A. Sharma and C. R. Murthy, “On finding a subset of non-defective items from a large population,” IEEE Transactions on Signal Processing , vol. 66, no. 21, p. 5762–5775, Nov. 2018

work page 2018
[23]

Almost disjunctive list-decoding codes,

A. G. D’yachkov, I. V . V orob’ev, N. Polyansky, and V . Y . Shchukin, “Almost disjunctive list-decoding codes,” Problems of Information Transmission, vol. 51, pp. 110–131, 2015

work page 2015
[24]

Group testing and sparse signal recovery,

A. C. Gilbert, M. A. Iwen, and M. J. Strauss, “Group testing and sparse signal recovery,” in Asilomar Conference on Signals, Systems and Computers. IEEE, 2008, pp. 1059–1063

work page 2008
[25]

Efficiently decodable non-adaptive group testing,

P. Indyk, H. Q. Ngo, and A. Rudra, “Efficiently decodable non-adaptive group testing,” in ACM-SIAM Symposium on Discrete Algorithms . SIAM, 2010, pp. 1126–1142

work page 2010
[26]

Group testing with random pools: Optimal two-stage algorithms,

M. M ´ezard and C. Toninelli, “Group testing with random pools: Optimal two-stage algorithms,” IEEE Transactions on Information Theory , vol. 57, no. 3, pp. 1736–1745, 2011

work page 2011
[27]

Group testing algorithms: Bounds and simulations,

M. Aldridge, L. Baldassini, and O. Johnson, “Group testing algorithms: Bounds and simulations,” IEEE Transactions on Information Theory , vol. 60, no. 6, pp. 3671–3687, 2014

work page 2014
[28]

Probability inequalities for sums of bounded random variables,

W. Hoeffding, “Probability inequalities for sums of bounded random variables,” The collected works of Wassily Hoeffding , pp. 409–426, 1994

work page 1994
[29]

Noisy adaptive group testing: Bounds and algorithms,

J. Scarlett, “Noisy adaptive group testing: Bounds and algorithms,” IEEE Transactions on Information Theory , vol. 65, no. 6, pp. 3646–3661, 2018

work page 2018
[30]

Optimal non-adaptive probabilistic group testing in general sparsity regimes,

W. H. Bay, J. Scarlett, and E. Price, “Optimal non-adaptive probabilistic group testing in general sparsity regimes,” Information and Inference: A Journal of the IMA , vol. 11, no. 3, pp. 1037–1053, 2022

work page 2022
[31]

A comparison of signalling alphabets,

E. N. Gilbert, “A comparison of signalling alphabets,” The Bell System Technical Journal , vol. 31, no. 3, pp. 504–522, 1952

work page 1952
[32]

Boucheron, G

S. Boucheron, G. Lugosi, and P. Massart, Concentration Inequalities: A Nonasymptotic Theory of Independence . Oxford University Press, 02 2013

work page 2013

[1] [1]

The detection of defective members of large populations,

R. Dorfman, “The detection of defective members of large populations,” The Annals of Mathematical Statistics , vol. 14, no. 4, pp. 436–440, 1943

work page 1943

[2] [2]

Pooling DNA in the identification of parents,

R. N. Curnow and A. P. Morris, “Pooling DNA in the identification of parents,” Heredity, vol. 80, no. 1, pp. 101–109, 1998

work page 1998

[3] [3]

A pooling strategy for heterozygote screening of the ΔF508 cystic fibrosis mutation,

C. Gille, K. Grade, and C. Coutelle, “A pooling strategy for heterozygote screening of the ΔF508 cystic fibrosis mutation,” Human Genetics, vol. 86, pp. 289–291, 1991

work page 1991

[4] [4]

An adaptive technique for local distribution,

J. Hayes, “An adaptive technique for local distribution,” IEEE Transactions on Communications , vol. 26, no. 8, pp. 1178–1186, 1978

work page 1978

[5] [5]

Born again group testing: Multiaccess communications,

J. Wolf, “Born again group testing: Multiaccess communications,” IEEE Transactions on Information Theory , vol. 31, no. 2, pp. 185–191, 1985

work page 1985

[6] [6]

Exact rule learning via boolean compressed sensing,

D. Malioutov and K. Varshney, “Exact rule learning via boolean compressed sensing,” in International Conference on Machine Learning . PMLR, 2013, pp. 765–773

work page 2013

[7] [7]

What’s hot and what’s not: Tracking most frequent items dynamically,

G. Cormode and S. Muthukrishnan, “What’s hot and what’s not: Tracking most frequent items dynamically,” ACM Transactions on Database Systems (TODS), vol. 30, no. 1, pp. 249–278, 2005

work page 2005

[8] [8]

Group testing: An information theory perspective,

M. Aldridge, O. Johnson, and J. Scarlett, “Group testing: An information theory perspective,” Foundations and Trends® in Communications and Information Theory , vol. 15, no. 3-4, pp. 196–392, 2019

work page 2019

[9] [9]

Bounds on the length of disjunctive codes

A. D’yachkov and V . Rykov, “Bounds on the length of disjunctive codes.” Problems of Information Transmission, vol. 18, no. 3, pp. 166–171, 1983

work page 1983

[10] [10]

Noise-resilient group testing: Limitations and constructions,

M. Cheraghchi, “Noise-resilient group testing: Limitations and constructions,” Discrete Applied Mathematics , vol. 161, no. 1-2, pp. 81–95, 2013

work page 2013

[11] [11]

How little does non-exact recovery help in group testing?

J. Scarlett and V . Cevher, “How little does non-exact recovery help in group testing?” in IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP) , 2017, pp. 6090–6094

work page 2017

[12] [12]

On the all-or-nothing behavior of Bernoulli group testing,

L. V . Truong, M. Aldridge, and J. Scarlett, “On the all-or-nothing behavior of Bernoulli group testing,” IEEE Journal on Selected Areas in Information Theory, vol. 1, no. 3, pp. 669–680, 2020

work page 2020

[13] [13]

The capacity of adaptive group testing,

L. Baldassini, O. Johnson, and M. Aldridge, “The capacity of adaptive group testing,” in IEEE International Symposium on Information Theory , 2013, pp. 2676–2680

work page 2013

[14] [14]

Non-adaptive probabilistic group testing with noisy measurements: Near-optimal bounds with efficient algorithms,

C. L. Chan, P. H. Che, S. Jaggi, and V . Saligrama, “Non-adaptive probabilistic group testing with noisy measurements: Near-optimal bounds with efficient algorithms,” in Allerton Conference on Communication, Control, and Computing , 2011, pp. 1832–1839

work page 2011

[15] [15]

A method for detecting all defective members in a population by group testing,

F. K. Hwang, “A method for detecting all defective members in a population by group testing,” Journal of the American Statistical Association , vol. 67, no. 339, pp. 605–608, 1972

work page 1972

[16] [16]

Optimal group testing,

A. Coja-Oghlan, O. Gebhard, M. Hahn-Klimroth, and P. Loick, “Optimal group testing,” in Conference on Learning Theory . PMLR, 2020, pp. 1374–1388

work page 2020

[17] [17]

Information-theoretic and algorithmic thresholds for group testing,

——, “Information-theoretic and algorithmic thresholds for group testing,” IEEE Transactions on Information Theory , vol. 66, no. 12, pp. 7911–7928, 2020

work page 2020

[18] [18]

Phase transitions in group testing,

J. Scarlett and V . Cevher, “Phase transitions in group testing,” in ACM-SIAM Symposium on Discrete Algorithms , 2016, pp. 40–53. 25

work page 2016

[19] [19]

Performance of group testing algorithms with near-constant tests per item,

O. Johnson, M. Aldridge, and J. Scarlett, “Performance of group testing algorithms with near-constant tests per item,” IEEE Transactions on Information Theory, vol. 65, no. 2, pp. 707–723, 2018

work page 2018

[20] [20]

Pooled testing to isolate infected individuals,

M. Aldridge, “Pooled testing to isolate infected individuals,” in Annual Conference on Information Sciences and Systems (CISS) . IEEE, 2021, pp. 1–5

work page 2021

[21] [21]

SAFFRON: A fast, efficient, and robust framework for group testing based on sparse-graph codes,

K. Lee, K. Chandrasekher, R. Pedarsani, and K. Ramchandran, “SAFFRON: A fast, efficient, and robust framework for group testing based on sparse-graph codes,” IEEE Transactions on Signal Processing , vol. 67, no. 17, pp. 4649–4664, 2019

work page 2019

[22] [22]

On finding a subset of non-defective items from a large population,

A. Sharma and C. R. Murthy, “On finding a subset of non-defective items from a large population,” IEEE Transactions on Signal Processing , vol. 66, no. 21, p. 5762–5775, Nov. 2018

work page 2018

[23] [23]

Almost disjunctive list-decoding codes,

A. G. D’yachkov, I. V . V orob’ev, N. Polyansky, and V . Y . Shchukin, “Almost disjunctive list-decoding codes,” Problems of Information Transmission, vol. 51, pp. 110–131, 2015

work page 2015

[24] [24]

Group testing and sparse signal recovery,

A. C. Gilbert, M. A. Iwen, and M. J. Strauss, “Group testing and sparse signal recovery,” in Asilomar Conference on Signals, Systems and Computers. IEEE, 2008, pp. 1059–1063

work page 2008

[25] [25]

Efficiently decodable non-adaptive group testing,

P. Indyk, H. Q. Ngo, and A. Rudra, “Efficiently decodable non-adaptive group testing,” in ACM-SIAM Symposium on Discrete Algorithms . SIAM, 2010, pp. 1126–1142

work page 2010

[26] [26]

Group testing with random pools: Optimal two-stage algorithms,

M. M ´ezard and C. Toninelli, “Group testing with random pools: Optimal two-stage algorithms,” IEEE Transactions on Information Theory , vol. 57, no. 3, pp. 1736–1745, 2011

work page 2011

[27] [27]

Group testing algorithms: Bounds and simulations,

M. Aldridge, L. Baldassini, and O. Johnson, “Group testing algorithms: Bounds and simulations,” IEEE Transactions on Information Theory , vol. 60, no. 6, pp. 3671–3687, 2014

work page 2014

[28] [28]

Probability inequalities for sums of bounded random variables,

W. Hoeffding, “Probability inequalities for sums of bounded random variables,” The collected works of Wassily Hoeffding , pp. 409–426, 1994

work page 1994

[29] [29]

Noisy adaptive group testing: Bounds and algorithms,

J. Scarlett, “Noisy adaptive group testing: Bounds and algorithms,” IEEE Transactions on Information Theory , vol. 65, no. 6, pp. 3646–3661, 2018

work page 2018

[30] [30]

Optimal non-adaptive probabilistic group testing in general sparsity regimes,

W. H. Bay, J. Scarlett, and E. Price, “Optimal non-adaptive probabilistic group testing in general sparsity regimes,” Information and Inference: A Journal of the IMA , vol. 11, no. 3, pp. 1037–1053, 2022

work page 2022

[31] [31]

A comparison of signalling alphabets,

E. N. Gilbert, “A comparison of signalling alphabets,” The Bell System Technical Journal , vol. 31, no. 3, pp. 504–522, 1952

work page 1952

[32] [32]

Boucheron, G

S. Boucheron, G. Lugosi, and P. Massart, Concentration Inequalities: A Nonasymptotic Theory of Independence . Oxford University Press, 02 2013

work page 2013