  The goal of the group testing problem is to identify a set of defective items
within a larger set of items, using suitably-designed tests whose outcomes
indicate whether any defective item is present. In this paper, we study how the
number of tests can be significantly decreased by leveraging the structural
dependencies between the items, i.e., by incorporating prior information. To do
so, we pursue two different perspectives: (i) As a generalization of the
uniform combinatorial prior, we consider the case that the defective set is
uniform over a \emph{subset} of all possible sets of a given size, and study
how this impacts the information-theoretic limits on the number of tests for
approximate recovery; (ii) As a generalization of the i.i.d.~prior, we
introduce a new class of priors based on the Ising model, where the associated
graph represents interactions between items. We show that this naturally leads
to an Integer Quadratic Program decoder, which can be converted to an Integer
Linear Program and/or relaxed to a non-integer variant for improved
computational complexity, while maintaining strong empirical recovery
performance.
