FR2.R6.4

List-Decoding Separable Matrices for Non-Adaptive Combinatorial Group Testing

Jinping Fan, Shanghai Normal University, China; Yujie Gu, Kyushu University, Japan; Ying Miao, University of Tsukuba, Japan; Zhebin Yu, Hitachi Astemo, Ltd., Japan

Session:
Group Testing 2

Track:
17: Group Testing

Location:
Sigma/Delta

Presentation Time:
Fri, 12 Jul, 12:30 - 12:50

Session Chair:
Soheil Mohajer, University of Minnesota
Abstract
In this paper, we introduce a new concept of \textit{list-decoding separable matrices} with strength $d$ and list size $L$, denoted as $(\Bar{d},L)$-LDSM, for non-adaptive combinatorial group testing, which is a generalized notion of several types of known test matrices such as $d$-disjunct matrices, $\Bar{d}$-separable matrices, and $d$-union-free codes with fast decoding. We first provide a two-step identifying algorithm for $(\Bar{d},L)$-LDSM of size $n\times m$ and show that it can determine all the $\le d$ positives among $m$ items in time $O(\max\{nm,nL^d\})$. Furthermore, we derive a lower bound on the largest rate of $(\Bar{d},L)$-LDSM for any $L\ge d\ge 2$ by random coding with expurgation. In particular, when $L=m^{1/d}$, the identifying algorithm of $(d,m^{1/d})$-LDSM is as efficient as that for $d$-disjunct matrices, while the rate of $(\bar{d},m^{1/d})$-LDSM can be significantly larger than that of $d$-disjunct matrices.
Resources