Efficient probabilistic group testing based on traitor tracing

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

11 Citations (Scopus)


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 ~ 2K 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.
Original languageEnglish
Title of host publication51st Annual Allerton Conference on Communication, Control, and Computing (Monticello IL, USA, October 2-3, 2013)
Place of PublicationPiscataway
PublisherInstitute of Electrical and Electronics Engineers
Number of pages8
ISBN (Print)978-1-4799-3409-6
Publication statusPublished - 2013


Dive into the research topics of 'Efficient probabilistic group testing based on traitor tracing'. Together they form a unique fingerprint.

Cite this