Optimal Algorithms for Two Group Testing Problems, and New Bounds on Generalized Superimposed Codes

Two variants of the well-known group testing problem are considered. In the first variant a finite set of items O and an unknown subset PsubeO are given, and one wants to identify the set P by asking the least number of questions of the form "Is |QcapP|=1?", where QsubeO. This problem naturally arises in the design of efficient contention resolution algorithms for certain random multiple-access communication systems [Berger et al. "Random multiple-access communication and group testing," IEEE Trans. Commun., vol. 32, no. 7, pp. 769-779, 1984]. In the second variant of the problem, the answer to the question "Is |QcapP|=1?" is correctly YES if |QcapP|=1 and NO if |QcapP|=0", and it is left to a (possibly malicious) adversary otherwise. This model was introduced in [Damaschke, "Randomized group testing for mutually obscuring defectives", Inf. Process. Lett., vol. 67, pp. 131-135, 1998], in the context of chemical compound testing. In this correspondence several algorithms for these group testing problems are presented, trying to optimize different measures of performance: The overall number of tests performed by the algorithm, the number of stages in which tests can be arranged, and the decoding complexity of identifying the elements of P from tests outcomes. Some of the given algorithms are optimal with respect to more than one of the above criteria. Instrumental to the results presented in the correspondence are new and improved bounds on certain generalization of superimposed codes introduced in [Dyachkov and Rykov, "A generalization of superimposed codes and its application to the multiple-access channel", in Proc. 1984 IEEE Int. Symp. Inf. Theory, pp. 62-64], [De Bonis and Vaccaro, "Constructions of generalized superimposed codes with applications to group testing and conflict resolution in multiple access channels", Theoretic. Comput. Sci., vol. 306, no. 1-3, pp. 223-243, 2003] a result that it is believed to be of independent interest