Subquadratic non-adaptive threshold group testing

We consider – a generalization of , which asks to identify a set of individuals in a population, by performing tests on pools of elements. Each test is represented by a subset of individuals and its output is if contains at least one positive element and otherwise. Threshold group testing is the natural generalization, introduced by P. Damaschke in 2005, arising when we are given a threshold and the answer to a test is if contains positives and otherwise. We give upper and lower bounds for this general problem, showing a complexity separation with the classical group testing. Next, we introduce a further generalization in which the goal is minimizing not only the number of tests, but also the number of thresholds which is related to the accuracy of the tests.