Symmetric group testing with noise

摘要

Group testing problem is to find all unknown defective elements (samples) of a search space, using subsets of the search space as tests (queries). We consider symmetric group testing (SGT), one of known group testing models. In SGT the response on a test ℱ equals 0 iff no defective elements belong to ℱ, equals 1 iff all elements of ℱ are defective, and equals {0, 1} otherwise. We derive a new upper bound on the number of tests needed to recover τ or less defective elements in presence of noise. Also, we recall the connection of SGT with cover-free codes, multiple access channel type A and fingerprinting codes for multimedia.