Efficient Probabilistic Group Testing Based on Traitor Tracing
This provides an efficient solution for group testing problems in fields like medical testing or quality control, though it appears incremental as it builds on existing traitor tracing methods.
The paper tackles the problem of identifying defective items in group testing by developing a framework based on traitor tracing techniques, achieving asymptotically T ~ 2K ln N tests to find K defectives out of N items with high probability. It also applies this framework to noisy and threshold models, often improving over prior results.
Inspired by recent results from collusion-resistant traitor tracing, we provide a framework for constructing efficient probabilistic group testing schemes. In the traditional group testing model, our scheme asymptotically requires T ~ 2 K ln N tests to find (with high probability) the correct set of K defectives out of N items. The framework is also applied to several noisy group testing and threshold group testing models, often leading to improvements over previously known results, but we emphasize that this framework can be applied to other variants of the classical model as well, both in adaptive and in non-adaptive settings.