Efficient Probabilistic Group Testing Based on Traitor Tracing
arXiv:1307.2438 · doi:10.1109/Allerton.2013.6736699
Abstract
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.
arXiv comment8 pages, 3 figures, 1 table
References in corpus (9)
- Boolean Compressed Sensing and Noisy Group Testing
- Note on Noisy Group Testing: Asymptotic Bounds and Belief Propagation Reconstruction
- The Capacity of Adaptive Group Testing
- Group Testing with Probabilistic Tests: Theory, Design and Application
- On the Saddle-point Solution and the Large-Coalition Asymptotics of Fingerprinting Games
- Dynamic Tardos Traitor Tracing Schemes
- Dynamic Traitor Tracing for Arbitrary Alphabets: Divide and Conquer
- Adaptive group testing as channel coding with feedback
- Dynamic Traitor Tracing Schemes, Revisited
Cited by in corpus (7)
- Capacities and Capacity-Achieving Decoders for Various Fingerprinting Games
- Asymptotics of Fingerprinting and Group Testing: Tight Bounds from Channel Capacities
- Dynamic Traitor Tracing Schemes, Revisited
- On the optimality of some group testing algorithms
- Asymptotics of Fingerprinting and Group Testing: Capacity-Achieving Log-Likelihood Decoders
- Optimal sequential fingerprinting: Wald vs. Tardos
- On a Couple of Unresolved Group Testing Conjectures