Non-Adaptive Multi-Stage Algorithm for Group Testing with Prior Statistics

In this seminar, I will present an efficient multi-stage algorithm for non-adaptive Group Testing (GT) with general correlated prior statistics. The proposed method can be applied to any correlated prior that can be represented as a trellis, such as finite state machines and Markov processes. To exploit the structure of the prior, we introduce a variation of the List Viterbi Algorithm (LVA), which enables accurate recovery using significantly fewer tests than existing methods. Our numerical results show that the proposed Multi-Stage GT (MSGT) algorithm achieves optimal Maximum A Posteriori (MAP) performance with practical computational complexity. In applications such as COVID-19 testing and sparse signal recovery, our method reduces the number of pooled tests by at least 25% compared to classical low-complexity GT algorithms. Additionally, we provide a theoretical analysis of the algorithm’s complexity, guaranteeing its efficiency.

M.Sc. student under the supervision of Prof. Alejandro Cohen.