2024/01/29 by Daniil Goshkoder, Goshkoder, Daniil, Nikita Polyanskii +3
Biochemistry, Genetics and Molecular Biology · Computer Science · Medicine · #Advanced biosensing and bioanalysis techniques #FOS: Computer and information sciences #Information Theory (cs.IT) #Privacy-Preserving Technologies in Data #SARS-CoV-2 detection and testing
paper · pdf · doi:10.48550/arxiv.2401.16540
openalex publication_date 2024/01/29 · openalex created_date 2024/02/01 · openalex updated_date 2026/07/28
This work focuses on non-adaptive combinatorial group testing, with a primary goal of efficiently identifying a set of at most d defective elements among a given set of n elements using the fewest possible tests. Non-adaptive combinatorial group testing often employs disjunctive matrices (DM) and separable matrices (SM). This paper discusses separable matrices and recently introduced list-decoding separable matrices (LDSM) with list size n1/d, which allow for non-adaptive identification of defectives with the decoding complexity linear in the number of tests and the number of elements. In our study, we distinguish two subclasses of these matrices: matrices which can be used when the number of defectives d is a priori known (d-SM and (d, n1/d)-LDSM), and matrices which can be used for any subset of at most d defectives (d-SM and (d, n1/d)-LDSM). Our contribution lies in deriving new lower bounds on the rates of d-SM, d-SM, (d, n1/d)-LDSM and (d, n1/d)-LDSM for an arbitrary number d ≥ 3 of defectives.