Nonadaptive group testing with lies: Probabilistic existence theorems

We consider a wide range of combinatorial group testing problems with lies including binary, additive and multiaccess channel group testing problems. We derive upper bounds for the number of tests in the optimal nonadaptive algorithms. The derivation is probabilistic and is therefore non-constructive; it does not provide the way of constructing optimal algorithms. In the asymptotic setting, we show that the leading term for the number of tests does not depend on the number of lies and it is thus the same as for the zero-lie case. However, the other terms in the asymptotic upper bounds depend on the number of lies and substantially influence the upper bounds in the non-asymptotic situation.