Efficient Probabilistic Group Testing Based on Traitor Tracing

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.

8 pages, 3 figures, 1 table

References in corpus (3)

• 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