Small-Error Cascaded Group Testing
This work provides theoretical foundations for cascaded group testing, a model relevant to applications like DNA sequencing and network tomography, but the results are primarily theoretical and incremental over existing group testing literature.
The paper studies cascaded group testing, where test outcomes indicate the first defective item in an ordered test. It establishes achievability bounds for various recovery criteria and provides a lower bound showing optimality up to logarithmic factors in the constrained test size setting.
Group testing concerns itself with the accurate recovery of a set of "defective" items from a larger population via a series of tests. While most works in this area have considered the classical group testing model, where tests are binary and indicate the presence of at least one defective item in the test, we study the cascaded group testing model. In cascaded group testing, tests admit an ordering, and test outcomes indicate the first defective item in the test under this ordering. Under this model, we establish various achievability bounds for several different recovery criteria using both non-adaptive and adaptive test designs when assuming both unconstrained and constrained test sizes. In the constrained test size setting, we also provide a lower bound showing our achievability result is optimal up to logarithmic factors.