Inference problems in the linear regime: Lessons from group testing
Matthew Aldridge
Modern techniques for inference are most effective for sparse problems, where the number of active inputs k is small compared to the total number of inputs n. Typically, this is represented mathematically by saying k = o(n) grows sublinearly as n gets large. But in many situations – for example, infected individuals in a pandemic that has spread through a population – it may be more reasonable to assume that k is a small but constant proportion of n. How might our inference problems look different in this linear regime? We look at this question through the example of pooled group testing – for example, screening for a disease by mixing samples together and testing the pooled samples. We consider both the nonadaptive (tests decided on in advance) and adaptive (tests performed in sequence) settings, and examine how algorithms and lower bounds differ from the sublinear regime.