An Analysis of the DD Algorithm for Group Testing with Size-Constrained Tests

In group testing, the goal is to identify a subset of defective items within a larger set of items based on tests whose outcomes indicate whether any defective item is present. This problem is relevant in areas such as medical testing, data science, communications, and more recently, utility in testing for COVID-19. Motivated by physical considerations, we consider a constrained setting in which each test can only contain a number of items up to some specified maximum value (Gandikota et al., 2019). While previous works have given recovery guarantees for this setting, there still exist significant gaps between the achievability and converse bounds when the maximum test size asymptotically increases as a function of the total number of items. In this paper, we partially close this gap by showing that the Definite Defectives (DD) algorithm, coupled with a suitable randomized test design, leads to an achievability result that improves on those of existing works, and is tight or near-tight in several regimes of interest.