REVIEW
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
Optimal adaptive group testing
read the original abstract
The group testing problem is concerned with identifying a small number $k \sim n^\theta$ for $\theta \in (0,1)$ of infected individuals in a large population of size $n$. At our disposal is a testing procedure that allows us to test groups of individuals. This paper considers two-stage designs where the test results of the first stage can inform the design of the second stage. We are interested in the minimum number of tests to recover the set of infected individuals w.h.p. Equipped with a novel algorithm for one-stage group testing from [Coja-Oghlan, Gebhard, Hahn-Klimroth \& Loick 2019], we propose a polynomial-time two-stage algorithm that matches the universal information-theoretic lower bound of group testing. This result improves on results from [M\'ezard \& Toninelli 2011] and resolves open problems prominently posed in [Aldridge, Johnson \& Scarlett 2019, Berger \& Levenshtein 2002, Damaschke \& Muhammad 2012].
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.