# Efficient designs for threshold group testing
without gap

Thach V. Bui , Yeow Meng Chee , and Van Khu Vu Thach V. Bui, Yeow Meng Chee,
and Van Khu Vu are with the Faculty of Engineering, National University of
Singapore, Singapore. Email<EMAIL_ADDRESS>
###### Abstract

Given $d$ defective items in a population of $n$ items with $d\ll n$, in
threshold group testing without gap, the outcome of a test on a subset of
items is positive if the subset has at least $u$ defective items and negative
otherwise, where $1\leq u\leq d$. The basic goal of threshold group testing is
to quickly identify the defective items via a small number of tests. In non-
adaptive design, all tests are designed independently and can be performed in
parallel. The decoding time in the non-adaptive state-of-the-art work is a
polynomial of $(d/u)^{u}(d/(d-u))^{d-u},d$, and $\log{n}$. In this work, we
present a novel design that significantly reduces the number of tests and the
decoding time to polynomials of $\min\\{u^{u},(d-u)^{d-u}\\},d$, and
$\log{n}$. In particular, when $u$ is a constant, the number of tests and the
decoding time are $O(d^{3}(\log^{2}{n})\log{(n/d)})$ and
$O\big{(}d^{3}(\log^{2}{n})\log{(n/d)}+d^{2}(\log{n})\log^{3}{(n/d)}\big{)}$,
respectively. For a special case when $u=2$, with non-adaptive design, the
number of tests and the decoding time are $O(d^{3}(\log{n})\log{(n/d)})$ and
$O(d^{2}(\log{n}+\log^{2}{(n/d)}))$, respectively. Moreover, with 2-stage
design, the number of tests and the decoding time are
$O(d^{2}\log^{2}{(n/d)})$.

##  I Introduction

The main objective of group testing is to find a small number of defective
items in a large population of items [1]. Defective items and non-defective
items are defined by context. For example, in Covid-19 scenario, defective
(respectively, non-defective) items are people who are positive (respectively,
negative) to Coronavirus. In standard group testing (SGT), a pool of items is
positive if there exists at least one defective item in the pool and negative
otherwise. In some problems [2, 3], there is a need for cooperation of at
least two defective items in an effort to achieve a certain goal. A test on a
set of items is positive if the certain goal is attained and negative
otherwise. This means the SGT model does not fit to these problems. Damaschke
[4] proposes a threshold group testing (TGT) model in which the outcome of a
test on a subset of items is positive if the subset has at least $u$ defective
items, negative if it has up to $\ell$ defective items, where $0\leq\ell<u$,
and arbitrary otherwise. The parameter $g=u-\ell-1$ is called the gap. It is
obvious that when $u=1$, TGT reduces to SGT. When $\ell+1=u$, TGT is called
_TGT without gap_.

In some problems [2, 3], there is a need for cooperation of at least two
defective items in an effort to achieve a certain goal. A test on a set of
items is positive if the certain goal is attained and negative otherwise. This
means the SGT model does not fit to these problems. A natural generalization
of SGT is to introduce a threshold for making a test positive. Damaschke [4]
proposes a threshold group testing (TGT) model in which the outcome of a test
on a subset of items is positive if the subset has at least $u$ defective
items, negative if it has up to $\ell$ defective items, where $0\leq\ell<u$,
and arbitrary otherwise. The parameter $g=u-\ell-1$ is called the gap. It is
obvious that when $u=1$, TGT reduces to SGT. When $\ell+1=u$, TGT is called
_TGT without gap_. We illustrate TGT without gap for $u=4$ versus standard
group testing in Fig. 1. The red and black dots represent defective and non-
defective items, respectively. A subset containing defective items and/or non-
defective items is a blue circle containing red and/or black dots. The outcome
of a test on a subset of items is positive ($+$) or negative ($-$). In SGT
(“Standard” in the figure), the outcome of a test on a subset of items is
positive if the subset has at least one red dot, and negative otherwise. In
TGT without gap (“Threshold” in the figure), the outcome of a test on a subset
of items is positive if the subset has at least $u=4$ red dots, negative if
the subset has up to $u-1=3$ red dots.

Figure 1: Illustration of threshold group testing without gap for $u=4$ versus
standard group testing.

There are many criteria in tackling group testing. Here we only mention four
main criteria. The first criterion is the number of stages. When the number of
stages is one, i.e., non-adaptive design, all tests are designed in priori and
independently. Since the tests in this design can be performed simultaneously,
it saves times, and therefore gives a significant advantage for some
applications with a fast response demand such as identifying infected persons
during pandemic [5]. Non-adaptive design has also been applied in other areas
such as computational and molecular biology [6], networking [7]. However, the
number of tests in non-adaptive design normally does not meet the information-
theoretic bound that multi-stage designs can obtain. In multi-stage design,
the design of tests in a stage depends on the design of the tests in the
previous designs and therefore time consuming is essentially unavoidable. The
second criterion is between deterministic and randomized design. Given the
same input, a deterministic design produces the same result while a randomized
one might not produce the same result because it includes a degree of
randomness in it. The third criterion is the setting of the defective set. The
combinatorial setting applies any configuration on the defective set under the
predefined constrains while the probabilistic setting applies some
distribution on the input items. Finally, both exact recovery and approximate
recovery are also an important criterion studied in group testing.

In this work, we consider non-adaptive and 2-stage designs, deterministic
design, combinatorial setting, and exact recovery. The formal problem
definition is presented in the subsequent section.

###  I-A Problem definition

We index the population of $n$ items from $1$ to $n$. Let
$[n]=\\{1,2,\ldots,n\\}$ and $P$ be the defective set with $|P|=d$. A test is
defined by a subset of items $S\subseteq[n]$. A pool with a negative
(positive) outcome is called a negative (positive) pool. The outcome of a test
on a subset of items is positive if the subset contains at least $u$ defective
items and is negative otherwise. Mathematically, the test outcome, denoted as
$\mathsf{test}(S)$, is positive if $|S\cap P|\geq u$ and negative if $|S\cap
P|<u$. This model is denoted as $(n,d,u)$-TGT. Note that $|P|$ can not be
smaller than $u$ because all tests yield negative otherwise.

To represent tests in a stage, measurement matrices are often used. A $t\times
n$ binary matrix $\mathcal{T}=(t_{ij})\in\\{0,1\\}^{t\times n}$ is defined as
a measurement matrix, where $n$ is the number of items and $t$ is the number
of tests, as follows. The $j$th item corresponds to the $j$th column of the
matrix. An entry $t_{ij}=1$ naturally means that item $j$ belongs to test $i$,
and $t_{ij}=0$ means otherwise. The outcome of all tests is
$\mathbf{y}=(y_{1},\ldots,y_{t})^{T}$, where $y_{i}=1$ if test $i$ is positive
and $y_{i}=0$ otherwise. An input vector
$\mathbf{x}=(x_{1},\ldots,x_{n})\in\\{0,1\\}^{n}$ represents $n$ items in
which $x_{j}=0$ if item $j$ is defective and $x_{j}=0$ otherwise for
$j\in[n]$. Let $\mathsf{supp}(\mathbf{v})=\\{j\mid v_{j}\neq 0\\}$ be the
support set for vector $\mathbf{v}=(v_{1},\ldots,v_{w})$. The AND operator
between two vectors of same size $\mathbf{z}=(z_{1},\ldots,z_{n})$ and
$\mathbf{z}^{\prime}=(z_{1}^{\prime},\ldots,z_{n}^{\prime})$ is
$\mathbf{z}\wedge\mathbf{z}^{\prime}=(z_{1}\wedge
z_{1}^{\prime},\ldots,z_{n}\wedge z_{n}^{\prime})$. Then the outcome vector
$\mathbf{y}$ is given by

$\displaystyle\mathbf{y}:=\begin{bmatrix}y_{1}\\\ \vdots\\\
y_{t}\end{bmatrix}$ $\displaystyle:=$
$\displaystyle\mathcal{T}\otimes\mathbf{x}$
$\displaystyle:=\begin{bmatrix}\mathcal{T}(1,:)\otimes\mathbf{x}\\\ \vdots\\\
\mathcal{T}(t,:)\otimes\mathbf{x}\end{bmatrix}$ $\displaystyle:=$
$\displaystyle\mathsf{test}(\mathcal{T},\mathsf{supp}(\mathbf{x}))$
$\displaystyle:=\begin{bmatrix}\mathsf{test}(\mathcal{T}(1,:)\wedge\mathbf{x})\\\
\vdots\\\ \mathsf{test}(\mathcal{T}(t,:)\wedge\mathbf{x})\end{bmatrix},$

where $\otimes$ and $\mathsf{test}(\cdot)$ are notations for the test
operations in non-adaptive $(n,u)$-TGT; namely,
$y_{i}:=\mathcal{T}(i,:)\otimes\mathbf{x}:=\mathsf{test}(\mathcal{T}(i,:)\wedge\mathbf{x})=1$
if $|\mathsf{supp}(\mathcal{T}(1,:))\cap\mathsf{supp}(\mathbf{x})\cap P|\geq
u$ and
$y_{i}:=\mathcal{T}(i,:)\otimes\mathbf{x}:=\mathsf{test}(\mathcal{T}(i,:)\wedge\mathbf{x})=0$
if $|\mathsf{supp}(\mathcal{T}_{i,*})\cap\mathsf{supp}(\mathbf{x})\cap P|<u$,
for $i=1,\ldots,t$. When $u=1$, $(n,u)$-TGT reduces to standard group testing
and we use $\odot$ instead of $\otimes$.

The procedure to get outcome vector $\mathbf{y}$ is called encoding and the
procedure to recover $\mathbf{x}$ from $\mathbf{y}$ and $\mathcal{T}$ is
called decoding. Our objective is to minimize $t$ and lower the time for
exactly recovering $P=\mathsf{supp}(\mathbf{x})$ from $\mathbf{y}$ by using
$\mathcal{T}$ with non-adaptive or 2-stage designs in $(n,d,u)$-TGT.

###  I-B Contributions

To the best of our knowledge, in the combinatorial setting and the
deterministic design, this is the first work that solves the threshold group
testing without gap problem with decoding complexity that scales in $u,d$, and
$\log{n}$. When $u$ is a constant, we present a non-adaptive design in which
the number of tests and the decoding time are
$O(d^{3}(\log^{2}{n})\log{(n/d)})$ and
$O\big{(}d^{3}(\log^{2}{n})\log{(n/d)}+d^{2}(\log{n})\log^{3}{(n/d)}\big{)}$,
respectively. Let $\min(g,h)=\min\\{\log{g},(\log_{h}{g})^{2}\\}$ and
$\min^{*}(u,d)=\min\left\\{u^{u},(d-u)^{d-u}\right\\}$. When $u$ is not a
constant, the number of tests and the decoding time are
$O\left(d(d-u)^{2}u^{2}\log{\frac{n}{d}}\times\min^{*}(u,d)\min(n,d-u+1)\min(n,u)\right)$
and $O\big{(}d(d-u)u^{2}\log{\frac{n}{d}}\min^{*}(u,d)$
$\min(n,u)\big{(}(d-u)\min(n,d-u+1)+\log^{2}{\frac{n}{d-u}}\big{)}\big{)}$,
respectively. These results are summarized in the following theorem.

######  Theorem 1.

Consider $(n,d,u)$-TGT, i.e., TGT without gap and the number of defective
items is $d$. There exists a non-adaptive design that can recover the
defective set with
$O\left(d(d-u)^{2}\log{\frac{n}{d}}\min(n,d-u+1)\min(n,u)\min^{*}(u,d)\right)$
tests in
$O\big{(}d(d-u)u^{2}\log{\frac{n}{d}}\min(n,u)\min^{*}(u,d)\big{(}(d-u)\min(n,d-u+1)+\log^{2}{\frac{n}{d-u}}\big{)}\big{)}$
time, where $\min(g,h)=\min\\{\log{g},(\log_{h}{g})^{2}\\}$ and
$\min^{*}(u,d)=\min\left\\{u^{u},(d-u)^{d-u}\right\\}$.

For a special case when $u=2$, with non-adaptive design, the number of tests
and the decoding time are $O(d^{3}(\log{n})\log{(n/d)})$ and
$O(d^{2}(\log{n}+\log^{2}{(n/d)}))$, respectively. Moreover, with 2-stage
design, the number of tests and the decoding time are
$O(d^{2}\log^{2}{(n/d)})$. These results are presented in the theorem below.

######  Theorem 2.

Consider $(n,d,\ell=1,u=2)$-TGT, i.e., TGT without gap and the number of
defective items is $d$. There exists a non-adaptive design that can recover
the defective set with $O\big{(}d^{3}\log{\frac{n}{d}}\cdot\min(n,d)\big{)}$
tests in $O\big{(}d^{2}\big{(}\log^{2}{\frac{n}{d}}+\min(n,d)\big{)}\big{)}$
time. For the 2-stage design, there exists a deterministic procedure that
recovers the defective set with $O\big{(}d^{2}\log^{2}{\frac{n}{d}}\big{)}$
tests in $O\big{(}d^{2}\log^{2}{\frac{n}{d}}\big{)}$ time.

Consider TGT without gap and with $|P|\leq d$. For non-adaptive design,
D’yachkov et al. [8] and Cheraghchi [9] shows that it is possible to recover
$P$ with $O(d^{2}\log{n})$ tests when $u$ is constant. Chen et al. [10]
propose a design with
$t=O\big{(}\big{(}\frac{d}{u}\big{)}^{u}\big{(}\frac{d}{d-u}\big{)}^{d-u}d\log{\frac{n}{d}}\big{)}$
tests to recover $P$ in $O(tun^{u})$ time, where $\mathrm{e}$ is the natural
logarithm base. Although the number of tests is exponential to $d$, the
decoding time is exponential to $d$ and linearly scales to $n^{u}$, this is
the first work that tackle TGT under the combinatorial setting, the
deterministic design, and the exact recovery criterion. Bui et al. [11] later
reduce the decoding complexity to $t\mathsf{poly}(d,\log{n})$. The numbers of
tests in these works are much larger than in our proposed designs. A
comparison of our proposed designs with previous works is summarized in Table
I.

| No. of
---
defectives
| No. of
---
stages
| Threshold
---
($u$)
Scheme |  | No. of tests
---
($t$)
| Decoding complexity
---
$d$ | 1 | $\geq 2$ | De Marco et al. [12] | $O\left(d^{3/2}\cdot\sqrt{\frac{d}{u}}\log{\frac{n}{d}}\right)$ | Not considered
Theorem 1 |  | $O\left(d(d-u)^{2}u^{2}\log{\frac{n}{d}}\times\min(n,d-u+1)\right.$
---
$\left.\times\min(n,u)\min\left\\{u^{u},(d-u)^{d-u}\right\\}\right)$
|
$O\big{(}d(d-u)u^{2}\log{\frac{n}{d}}\min(n,u)\min\left\\{u^{u},(d-u)^{d-u}\right\\}$
---
$\times\big{(}(d-u)\min(n,d-u+1)+\log^{2}{\frac{n}{d-u}}\big{)}\big{)}$
2 | Theorem 2 | $O\big{(}d^{3}\log{\frac{n}{d}}\cdot\min(n,d)\big{)}$ | $O\big{(}d^{2}\big{(}\log^{2}{\frac{n}{d}}+\min(n,d)\big{)}\big{)}$
2 | Theorem 2 | $O\big{(}d^{2}\log^{2}{\frac{n}{d}}\big{)}$ | $O\big{(}d^{2}\log^{2}{\frac{n}{d}}\big{)}$
$\leq d$ | 1 | $\geq 2$ | D’yachkov et al. [8] | $O\left(d^{2}\log{n}\cdot\frac{(u-1)!4^{u}}{(u-2)^{u}(\ln{2})^{u}}\right)$ | Not considered
Cheraghchi [9] | $O((8u)^{u}d^{2}\log{d}\cdot\log{\frac{n}{d}})$ | Not considered
Chen et al. [10] | $O\left(\left(\frac{d}{u}\right)^{u}\left(\frac{d}{d-u}\right)^{d-u}d\log{\frac{n}{d}}\right)$ | $O(tun^{u})$
Bui et al. [11] | $O\left(\left(\frac{d}{u}\right)^{u}\left(\frac{d}{d-u}\right)^{d-u}d^{3}\log{n}\cdot\log{\frac{n}{d}}\right)$ | $t\times\mathsf{poly}(d,\log{n})$

TABLE I: Comparison with existing work under the deterministic design, the
combinatorial setting, and the exact recovery setting. Here, we denote
$\min(g,h)=\min\\{\log{g},(\log_{h}{g})^{2}\\}$.

###  I-C Related work

Consider a population of $n$ items and a set of up to $d$ defective items,
i.e., $|P|\leq d$. In SGT, it is possible to obtain the information-theoretic
number of tests $O(d\log{(n/d)})$ and identify all defective items by using
2-stage designs [13]. In non-adaptive design, although the lower bound of the
number of tests is $O(d^{2}\log_{d}{n})$ [14], the best practice for attaining
explicit construction is $O(d^{2}\log{n})$ [15]. There is a body of
literatures working on attaining $O(d^{2}\log{n})$ tests and decoding time of
$\mathsf{poly}(d,\log{n})$ such as [16, 17, 18, 19, 20].

Consider TGT without gap. When $|P|=d$, De Marco et al. [12] propose a scheme
with no decoding procedure that requires
$O\left(d^{3/2}\cdot\sqrt{\frac{d}{u}}\log{\frac{n}{d}}\right)$ tests. There
are some works [21, 22] that consider the case $|P|=d$ under the probabilistic
setting with some models applied on the gap $g$ and achieve lower numbers of
tests compared to ours. However, either their decoding complexity scales
linearly to the number of items [21] or an external look-up matrix of size
$O(u\log{n})\times\binom{n}{u}$ is required [22].

##  II Preliminaries

###  II-A Notations

For consistency, we use capital calligraphic letters for matrices, non-capital
letters for scalars, bold letters for vectors, and capital letters for sets.
All matrix and vector entries are binary. The frequently used notations are
listed in Table II.

| Notation
---
| Description
---
$n$ | Number of items
$d$ | Number of defective items
$\mathbf{x}=(x_{1},\ldots,x_{n})^{T}$ | Binary representation of $n$ items
$\mathsf{supp}(\mathbf{v})=\\{j\mid v_{j}\neq 0\\}$ | The support set for vector $\mathbf{v}=(v_{1},\ldots,v_{w})$
$\mathsf{vecc}(A)$ | A $1\times n$ support vector for set $A$ such that $\mathsf{supp}(\mathsf{vecc}(A))=A$.
$u$ | Threshold in non-adaptive $(n,u)$-TGT model
$P=\\{p_{1},p_{2},\ldots,p_{|P|}\\}$ |  | Set of defective items; Cardinality of $P$ is $|P|=d$
---
$N=[n]=\\{1,\ldots,n\\}$ | Set of $n$ items
$\otimes_{u}$ |  | Operation related to non-adaptive $(n,u)$-TGT (to be defined later)
---
$\mathcal{T}(i,:),\mathcal{M}(i,:)$ | Row $i$ of matrix $\mathcal{T}$, row $i$ of matrix $\mathcal{M}$
$\mathcal{T}(:,j),\mathcal{M}(:,j)$ | Column $j$ of matrix $\mathcal{T}$, column $j$ of matrix $\mathcal{M}$
$\min(g,h)$ | $\min\\{\log{g},(\log_{h}{g})^{2}\\}$
$\mathrm{e}$ | The natural logarithm base.

TABLE II: Notations frequently used in this paper.

###  II-B Disjunct and list-disjunct matrices

Disjunct matrices are a powerful tool to tackle the standard and threshold
group testing problem [10, 9, 11]. They were first introduced by Kautz and
Singleton [23] and then generalized by Stinson and Wei [24] and D’yachkov et
al. [25]. The formal definition of a disjunct matrix is as follows.

######  Definition 1.

An $m\times n$ binary matrix $\mathcal{M}$ is called a $k$-disjunct matrix if,
for any two disjoint subsets $S_{1},S_{2}\subset[n]$ such that $|S_{1}|=k$ and
$|S_{2}|=1$, there exists at least one row in which there are all 1’s among
the columns in $S_{2}$ while all the columns in $S_{1}$ have 0’s, i.e.,
$\left|\bigcap_{j\in
S_{2}}\mathsf{supp}\left(\mathcal{M}(:,j)\right)\big{\backslash}\bigcup_{j\in
S_{1}}\mathsf{supp}\left(\mathcal{M}(:,j)\right)\right|\geq 1$.

When $\mathcal{M}$ is a $d$-disjunct matrix and $|\mathbf{x}|\leq d$, there
exists an efficient procedure to recover $\mathsf{supp}(\mathbf{x})$ from
$\mathcal{M}\odot\mathbf{x}$ as follows.

######  Theorem 3.

[18, Theorem 3.3] There exists a Monte-Carlo construction of a $k$-disjunct
matrix $\mathcal{M}\in\\{0,1\\}^{m\times n}$ with
$m=O(k^{2}\min\\{\log{n},(\log_{k}{n})^{2}\\})$, that allows decoding in
$O(m+k\log^{2}{(n/k)})$ time.

List-disjunct matrices are a relaxation of disjunct matrices [26, 27, 13, 16,
28]. In particular, once we set $|S_{2}|=\ell\geq 1$ in Definition 1, matrix
$\mathcal{M}$ is called a $(k,\ell)$-list disjunct matrix. Given an input
vector $\mathbf{x}$ with $P=\mathsf{supp}(\mathbf{x})$ and the test outcome
vector $\mathcal{M}\odot\mathbf{x}$, there exists a decoding procedure that
returns set $L$ such that $L\cap P=P$ and $|L|\leq k+\ell-1$. Cheraghchi and
Nakos [18] present an efficient encoding and decoding scheme for list disjunct
matrices as follows.

######  Theorem 4.

[18, Theorem 3.2] There exists a Monte-Carlo construction of a $(k,k)$-list
disjunct matrix $\mathcal{M}\in\\{0,1\\}^{m\times n}$ with
$m=O(k\log{(n/k)})$, that allows decoding in $O(k\log^{2}{(n/k)})$ time.

For any vector $\mathbf{x}$ with $|\mathbf{x}|\leq k$, let
$\mathrm{Dec}(\mathcal{M}\odot\mathbf{x},\mathcal{M})$ be an exact recovery
decoding procedure that returns $\mathsf{supp}(\mathbf{x})$ when $\mathcal{M}$
is a $k$-disjunct matrix or returns set $L$ with
$L\cap\mathsf{supp}(\mathbf{x})=\mathsf{supp}(\mathbf{x})$ and $|L|\leq 2k$
when $\mathcal{M}$ is a $(k,k)$-list disjunct matrix.

##  III Non-adaptive design

In this section, we present an algorithm with up to $O(u^{u}d^{3}\log^{3}{n})$
decoding time to find the defective set.

###  III-A Comments on the technique using auxiliary subset

In the seminal work of threshold group testing, Damaschke [4] proposed an idea
of using a set $U$ of $u-1$ defective items as auxiliary pool in the standard
group testing strategy. Then the number of tests and the decoding time for
identifying the defective set are the same as the standard group testing
strategy. This cannot be applied to non-adaptive setting because the defective
items in the set of $u-1$ defective items $U$ can not be identified by this
way. Indeed, let $x\in U$ and $\mathcal{M}$ be a $d$-disjunct matrix. Because
of the disjunctiveness property of $\mathcal{M}$, there exists a test in which
it contains $x$ and none of $P\setminus\\{x\\}$. By adding the $u-1$ items in
$U$ into this test, the number of defective items in this test is $u-1$
because $x\in U$. Consequently, the outcome of this test is negative. Thus,
the defective item $x$ is identified as negative. We reiterate that any work
using the auxiliary subset proposed by Damaschke for the non-adaptive setting
may encounter the same mistake. There is a simple way to remedy this. Given a
known $u$ defective items, we use $u$ distinct auxiliary pools of $u-1$
defective items in the standard group testing strategy. Then the defective set
is the union set of $u$ defective sets obtained from the decoding procedures
in the standard group testing strategy.

###  III-B Single selectors

To attain a design with an efficient encoding and decoding algorithm, we
propose a notation called _single selector_.

######  Definition 2.

Given integers $m,d$, and $n$, with $1\leq m\leq d\leq n$. A Boolean matrix is
called _an $(m,d,n)$-single selector_ if for any arbitrary set $D\subseteq[n]$
with $|D|=d$, there exists a row in $\mathcal{M}$ such that it contains
exactly $m$ items in $D$.

The following lemma presents the existence of single selectors by
probabilistic construction (proved in the appendix).

######  Lemma 1.

Given integers $m,d$, and $n$, with $1\leq m<d\leq n$, there exists an
$(m,d,n)$-single selector with
$O\big{(}\min\left\\{m^{m},(d-m)^{d-m}\right\\}d\log{\frac{n}{d}}\big{)}$
rows. When $m=d$, $t=O\big{(}d\log{\frac{n}{d}}\big{)}$.

###### Proof.

Consider a binary Bernoulli matrix $\mathcal{M}=(m_{ij})$ of size $t\times n$
in which $\Pr[m_{ij}=1]=p$ and $\Pr[m_{ij}=0]=1-p$. Consider a set $D$ of $d$
columns in $\mathcal{M}$. Let the event that a row does not contain exactly
$m$ ones in $D$ be _the bad event_. The probability that the bad event happens
is:

$1-\binom{d}{m}p^{m}(1-p)^{d-m}.$

By setting $p=1/d$, we get

$\displaystyle\binom{d}{m}p^{m}(1-p)^{d-m}=\binom{d}{m}\left(\frac{1}{d}\right)^{m}\left(1-\frac{1}{d}\right)^{d-m}$
$\displaystyle\geq\left(\frac{d}{m}\right)^{m}\left(\frac{1}{d}\right)^{m}\left(1-\frac{1}{d}\right)^{d-m}=\frac{1}{m^{m}}\left(1-\frac{1}{d}\right)^{d}\left(1+\frac{1}{d-1}\right)^{m}$
(1)
$\displaystyle\geq\frac{1}{m^{m}}\times\mathrm{e}\left(1-\frac{1}{d}\right)\left(1+\frac{1}{d-1}\right)^{m}=\frac{\mathrm{e}}{m^{m}}\left(1+\frac{1}{d-1}\right)^{m-1}$
(2) $\displaystyle\geq\frac{\mathrm{e}}{m^{m}},$

where $\mathrm{e}$ is base of the natural logarithm. Equation (1) is obtained
because $\left(\frac{a}{b}\right)^{b}\leq\binom{a}{b}$ for $0<a\leq b$. We get
(2) because
$\mathrm{e}\big{(}1-\frac{1}{d}\big{)}\leq\big{(}1-\frac{1}{d}\big{)}^{d}$.
Consequently, the probability that the bad event happens for the $t$ rows with
respect to $D$ is

$\left(1-\binom{d}{m}p^{m}(1-p)^{d-m}\right)^{t}\leq\left(1-\frac{\mathrm{e}}{m^{m}}\right)^{t}\leq\exp\left(-\frac{\mathrm{e}t}{m^{m}}\right),$

because $1-x\leq e^{-x}$ for any $x>0$. Therefore, the probability that
$\mathcal{M}$ is not an $(m,d,n)$-single selector, i.e., there exists at least
one subset $D\subseteq[n]$ with $|D|=d$ such that the bad event happens for
the $t$ rows, is up to:

$\binom{n}{d}\left(1-\binom{d}{m}p^{m}(1-p)^{d-m}\right)^{t}\leq\left(\frac{\mathrm{e}n}{d}\right)^{d}\exp\left(-\frac{\mathrm{e}t}{m^{m}}\right),$
(3)

where the last equation is obtained because
$\binom{a}{b}\leq\left(\frac{\mathrm{e}a}{b}\right)^{b}$ for $0<a\leq b$. To
ensure that there exists an $(m,d,n)$-single selector $\mathcal{M}$, one needs

$\left(\frac{\mathrm{e}n}{d}\right)^{d}\exp\left(-\frac{\mathrm{e}t}{m^{m}}\right)<1\Longleftrightarrow\frac{m^{m}d}{\mathrm{e}}\left(1+\log{\frac{n}{d}}\right)<t.$
(4)

Thus, we can choose
$t=\lceil\frac{m^{m}d}{\mathrm{e}}\big{(}1+\log{\frac{n}{d}}\big{)}\rceil+1=O\big{(}m^{m}d\log{\frac{n}{d}}\big{)}$
to satisfy (4).

We can easily create a $(d-m,d,n)$-single selector
$\bar{\mathcal{M}}=(\bar{m}_{ij})$ from a $t\times n$ $(m,d,n)$-single
selector $\mathcal{M}=(m_{ij})$ by inverting all entries in $\mathcal{M}$,
i.e., $\bar{m}_{ij}=1-m_{ij}$ for $i\in[t]$ and $j\in[n]$.

When $m=d$, we choose $p=d/(d+1)$ then (3) becomes

$\displaystyle\binom{n}{d}\left(1-\binom{d}{m}p^{m}(1-p)^{d-m}\right)^{t}$
$\displaystyle=\binom{n}{d}\left(1-\left(\frac{d}{d+1}\right)^{d}\right)^{t}\leq\left(\frac{\mathrm{e}n}{d}\right)^{d}\exp\left(-t\left(\frac{d}{d+1}\right)^{d}\right).$

This inequality holds if we choose
$t=\lceil\mathrm{e}d\left(1+\log{\frac{n}{d}}\right)\rceil+1=O\big{(}d\log{\frac{n}{d}}\big{)}$
because:

$\displaystyle
t>\mathrm{e}d\left(1+\log{\frac{n}{d}}\right)\geq\left(1+\frac{1}{d}\right)^{d}\log{\left(\frac{\mathrm{e}n}{d}\right)^{d}}$
$\displaystyle\Longrightarrow\left(\frac{\mathrm{e}n}{d}\right)^{d}\exp\left(-\frac{\mathrm{e}t}{m^{m}}\right)<1.$

This completes our proof.

∎

###  III-C Non-adaptive design

Here we present a non-adaptive design to tackle TGT without gap and summarize
it in Theorem 1. When $u=d$, it has been known that the $d$ defective items
can be found by using a $d$-disjunct matrix and its complementary matrix [11,
Lemma 1]. Because of Theorem 3, it takes $O(d^{2}\min(d,n))$ tests to identify
all $d$ defective items in $O(d^{2}\min(d,n)+d\log^{2}{(n/d)})$ time. This
satisfies the claims in Theorem 1. Therefore, we only consider the case $u<d$
to prove Theorem 1.

####  III-C1 Main idea

Our objective is first creating a test that contains exactly $u$ defective
items. From these $u$ defective items, we create $u$ sets
$S_{1},\ldots,S_{u}\subseteq[n]$ of items such that each set contains exactly
$u-1$ defective items and the sets of the defective items in these $u$ tests
are distinct, i.e., $S_{i}\cap P\neq S_{i^{\prime}}\cap P$ for any $i\neq
i^{\prime}$. The by augmenting $S_{i}$ to a $(d-u)$-disjunct matrix
$\mathcal{M}$ for testing and decoding, we can recover set $P\setminus S_{i}$.
Therefore, the defective set $P$ can be recover by setting
$P=\bigvee_{i=1}^{u}(P\setminus S_{i})$.

####  III-C2 Encoding

In the pursuit of attaining an efficient decoding procedure, we initialize the
following matrices:

  * •

Matrix $\mathcal{A}$ of size $a\times n$ is a $(d,u,n)$-single selector, where
$a=O\left(\min\left\\{u^{u},(d-u)^{d-u}\right\\}d\log{\frac{n}{d}}\right)$ and
set $0^{0}=1$ for simplicity.

  * •

Matrix $\mathcal{M}$ and $\mathcal{B}$ of size $m\times n$ and $b\times n$ are
$(d-u+1)$-disjunct and $u$-disjunct matrices, respectively. Specifically,
$m=O\big{(}(d-u)^{2}\min(n,d-u+1)\big{)}$ and
$b=O\big{(}u^{2}\min(n,u)\big{)}$.

The whole encoding procedure is illustrated in Fig. 2. In this figure, we set
$u=3$, $d=5$, and $P=\\{j_{1},j_{2},j_{3},j_{4},j_{5}\\}$. Matrix
$\mathcal{A}$ has some special row that contains only $u$ defective items,
says $j_{1},j_{3}$, and $j_{5}$, in the defective set $P$. Let
$S=\\{j_{1},j_{2},j_{5}\\}$. Since matrix $\mathcal{B}$ is $u$-disjunct, there
exists $u=3$ distinct private rows such that the first row (squared by a solid
rectangle) contains $j_{1}$ but does not contain the items in
$S\setminus\\{j_{1}\\}$, the second row (squared by a long dash dot dot
rectangle) contains $j_{3}$ but does not contain the items in
$S\setminus\\{j_{3}\\}$, and the third row (squared by a square dot rectangle)
contains $j_{5}$ but does not contain the items in $S\setminus\\{j_{5}\\}$. By
applying the exclusion operator (defined later) to $\mathcal{A}$ and
$\mathcal{B}$, the special row in $\mathcal{A}$ and the $u$ private rows in
$\mathcal{B}$ generate $u$ rows in which each row contains $u-1$ items in $S$.
The set of the defective items in each row is the complementary set of the
defective set in its corresponding private row. In particular, the first,
second, and third rows contain $S\setminus\\{j_{1}\\},S\setminus\\{j_{3}\\}$,
and $S\setminus\\{j_{5}\\}$, respectively. These rows are depicted in $u=3$
matrices and their corresponding solid, long dash dot dot, and square dot
rectangles, after the first three arrows. By augmenting each row with a
$(d-u+1)$-disjunct matrix $\mathcal{M}$, the new matrix will contain at least
$d-u+1$ rows, each row contains $u$ defective items. Among these $u$ defective
items, there always exist $u-1$ defective items in the row augmented with
$\mathcal{M}$. Testing each new matrix result in an outcome vector that can be
converted into tests in standard group testing. From example, for the row
containing $S\setminus\\{j_{1}\\}$, the outcome vector for testing the new
matrix generated by it and $\mathcal{M}$ is
$\mathcal{M}=\mathsf{vecc}(P\setminus(S\setminus\\{j_{1}\\}))$.

Figure 2: Illustration of the encoding procedure for $u=3,d=5$, and
$P=\\{j_{1},j_{2},j_{3},j_{4},j_{5}\\}$.

We define some notations as follows. The exclusion-wise operator between two
vectors of same size $\mathbf{z}=(z_{1},\ldots,z_{n})$ and
$\mathbf{z}^{\prime}=(z_{1}^{\prime},\ldots,z_{n}^{\prime})$ is
$\mathbf{z}\circ\mathbf{z}^{\prime}=(z_{1}^{\prime}\oplus(z_{1}^{\prime}\wedge
z_{1}),\ldots,z_{n}^{\prime}\oplus(z_{n}^{\prime}\wedge z_{n}))$, where
$\oplus$ is the XOR-bitwise operator. In other words,
$\mathsf{supp}(\mathbf{z}\circ\mathbf{z}^{\prime})=\mathsf{supp}(\mathbf{z}^{\prime})\setminus\mathsf{supp}(\mathbf{z})$.
Then the exclusion operator between two matrices $\mathcal{A}$ and
$\mathcal{B}$ is defined as
$\mathcal{B}\circ\mathcal{A}:=\begin{bmatrix}\mathcal{B}\circ\mathcal{A}(1,:)\\\
\vdots\\\ \mathcal{B}\circ\mathcal{A}(a,:)\end{bmatrix}$, where
$\mathcal{B}\circ\mathcal{A}(i,:):=\begin{bmatrix}\mathcal{B}(1,:)\circ\mathcal{A}(i,:)\\\
\vdots\\\ \mathcal{B}(b,:)\circ\mathcal{A}(i,:)\end{bmatrix}$ for
$i=1,\ldots,a$.

Similarly, the OR-wise operator between two vectors of same size
$\mathbf{z}=(z_{1},\ldots,z_{n})$ and
$\mathbf{z}^{\prime}=(z_{1}^{\prime},\ldots,z_{n}^{\prime})$ is
$\mathbf{z}\vee\mathbf{z}^{\prime}=(z_{1}\vee z_{1}^{\prime},\ldots,z_{n}\vee
z_{n}^{\prime})$. In other words,
$\mathsf{supp}(\mathbf{z}\vee\mathbf{z}^{\prime})=\mathsf{supp}(\mathbf{z})\cup\mathsf{supp}(\mathbf{z}^{\prime})$.
The OR operator between two matrices $\mathcal{A}$ and $\mathcal{B}$ is then
defined as
$\mathcal{B}\vee\mathcal{A}:=\begin{bmatrix}\mathcal{B}\vee\mathcal{A}(1,:)\\\
\vdots\\\ \mathcal{B}\vee\mathcal{A}(a,:)\end{bmatrix}$, where
$\mathcal{B}\vee\mathcal{A}(i,:):=\begin{bmatrix}\mathcal{B}(1,:)\vee\mathcal{A}(i,:)\\\
\vdots\\\ \mathcal{B}(b,:)\vee\mathcal{A}(i,:)\end{bmatrix}$ for
$i=1,\ldots,a$.

The measurement matrix is defined as

$\mathcal{T}:=\begin{bmatrix}\mathcal{A}\\\ \mathcal{B}\circ\mathcal{A}\\\
\mathcal{M}\vee(\mathcal{B}\circ\mathcal{A})\end{bmatrix},$

and the outcome vector is

$\mathbf{y}:=\mathsf{test}(\mathcal{T})=\begin{bmatrix}\vdots\\\
\mathsf{test}(\mathcal{A}(i,:))\\\
\mathsf{test}(\mathcal{B}(i^{\prime},:)\circ\mathcal{A}(i,:))\\\
\mathsf{test}(\mathcal{M}\vee(\mathcal{B}(i^{\prime},:)\circ\mathcal{A}(i,:)))\\\
\vdots\end{bmatrix},$ (5)

where $i=1,\ldots,a$ and $i^{\prime}=1,\ldots,b$.

####  III-C3 Decoding

For each $i\in\\{1,\ldots,a\\}$ and $i^{\prime}\in\\{1,\ldots,b\\}$, if
$\mathsf{test}(\mathcal{A}(i,:))$ is positive and
$\mathsf{test}(\mathcal{B}(i^{\prime},:)\circ\mathcal{A}(i,:))$ is negative,
set
$S_{i,i^{\prime}}=\mathrm{dec}(\mathsf{test}(\mathcal{M}\vee(\mathcal{B}(i^{\prime},:)\circ\mathcal{A}(i,:))),\mathcal{M})$
and add $S_{i,i^{\prime}}$ into the defective set $S$.

####  III-C4 Correctness

We first state a useful lemma in utilizing disjunct matrices to identify
defective items with auxiliary set. The full proof and complexity are
presented in the full version.

######  Lemma 2.

Consider $(n,\bar{p},u)$-TGT, i.e., TGT without gap and the number of
defective items is at most $p$. Let $P$ and $\mathcal{M}$ be a defective set
and a $t\times n$ $p$-disjunct matrix, where $|P|\leq p$. Let
$\mathbf{x}\in\\{0,1\\}^{n}$ be an input vector and
$\mathbf{y}=\mathsf{test}(\mathcal{M}\vee\mathbf{x})$. Then if
$\mathsf{test}(\mathbf{x})=0$, for any decoding procedure with the exact
recovery in standard group testing with the measurement matrix $\mathcal{M}$
and the outcome vector $\mathbf{y}$, the returned defective set is
$P\setminus\mathsf{supp}(\mathbf{x})$ if $|\mathsf{supp}(\mathbf{x})\cap
P|=u-1$ and an empty set if $|\mathsf{supp}(\mathbf{x})\cap P|<u-1$.

As described in Section III-C1, we need to prove that there exist $u$ sets
$S_{1},\ldots,S_{u}\subseteq[n]$ such that each set contains exactly $u-1$
defective items and $S_{i}\cap P\neq S_{i^{\prime}}\cap P$ for any $i\neq
i^{\prime}$. Indeed, since $\mathcal{A}$ is a $(d,u,n)$-single selector and
$|P|=d$, there exists a row $r^{*}$ such that
$|\mathsf{supp}(\mathcal{A}(r^{*},:))\cap P|=u$. Let
$Q=\mathsf{supp}(\mathcal{A}(r^{*},:))\cap P$. Because $\mathcal{B}$ is a
$u$-disjunct matrix, for any $q\in Q$, there exists a row, denoted as $r_{q}$,
such that $\mathsf{supp}(\mathcal{B}(r_{q},:))\cap Q=\\{q\\}$. On the other
hand,
$\mathsf{supp}(\mathcal{B}(r_{q},:)\circ\mathcal{A}(r^{*},:))=(\mathsf{supp}(\mathcal{A}(r^{*},:))\setminus\mathsf{supp}(\mathcal{B}(r_{q},:))\cup(\mathsf{supp}(\mathcal{B}(r_{q},:)\setminus\mathsf{supp}(\mathcal{A}(r^{*},:)))$.
Therefore, $\mathsf{supp}(\mathcal{B}(r_{q},:)\circ\mathcal{A}(r^{*},:))\cap
P=(\mathsf{supp}(\mathcal{A}(r^{*},:))\cap
P)\setminus(\mathsf{supp}(\mathcal{B}(r_{q},:)\cap P)=Q\setminus\\{q\\}$.
Since $|Q|=u$, there thus exist $u$ sets $S_{1},\ldots,S_{u}\subseteq[n]$ such
that each set contains exactly $u-1$ defective items and $S_{i}\cap P\neq
S_{i^{\prime}}\cap P$ for any $i\neq i^{\prime}$. On the other hand,
$\mathsf{test}(\mathcal{A}(r^{*},:))$ is positive and
$\mathsf{test}(\mathcal{B}(r_{q},:)\circ\mathcal{A}(r^{*},:))$ is negative, by
using Lemma 2 with the fact that $\mathcal{M}$ is a $(d-u+1)$-disjunct matrix,
we get
$\mathsf{test}(\mathcal{M}\vee(\mathcal{B}(r_{q},:)\circ\mathcal{A}(r^{*},:)))=\mathsf{test}(\mathcal{M},Q\setminus\\{q\\})$.
Therefore, set
$S_{r^{*},r_{q}}=\mathrm{dec}(\mathsf{test}(\mathcal{M}\vee(\mathcal{B}(r_{q},:)\circ\mathcal{A}(r^{*},:))),\mathcal{M})$
is $P\setminus(Q\setminus\\{q\\})$. It is straightforward that
$P=\bigcup_{q\in Q}P\setminus(Q\setminus\\{q\\})$. This implies the set $S$
always contains all defective items.

To complete our proof, we need to show that the decoding procedure never adds
false defective items to the defective set. Consider $i\in[a]$. If
$|\mathsf{supp}(\mathcal{A}(i,:))\cap P|<u$ then
$\mathsf{test}(\mathcal{A}(i,:))$ is negative. Therefore, no items are added
to $S$. If $\mathsf{test}(\mathcal{A}(i,:))$ is positive and
$\mathsf{test}(\mathcal{B}(i^{\prime},:)\circ\mathcal{A}(i,:))$ is positive,
again, no items are added to $S$. If $\mathsf{test}(\mathcal{A}(i,:))$ is
positive and $\mathsf{test}(\mathcal{B}(i^{\prime},:)\circ\mathcal{A}(i,:))$
is negative, there are only two cases:

  * •

$|\mathcal{A}(i,:)\cap P|=u$ and
$|\mathsf{supp}(\mathcal{B}(i^{\prime},:)\circ\mathcal{A}(i,:))\cap P|<u$.

  * •

$|\mathcal{A}(i,:)\cap P|>u$ and
$|\mathsf{supp}(\mathcal{B}(i^{\prime},:)\circ\mathcal{A}(i,:))\cap P|<u$.

In both cases, by Lemma 2, the returned defective set by using any decoding
procedure with the exact recovery in standard group testing never contains
negative items.

####  III-C5 Complexity

By using Lemma 1,
$a=O\left(\min\left\\{u^{u},(d-u)^{d-u}\right\\}d\log{\frac{n}{d}}\right)$,
where we set $0^{0}=1$ for simplicity. As in Theorem 3, a $t\times n$
$p$-disjunct matrix $\mathcal{M}$ can be efficiently decoded in
$O\big{(}t+p\log^{2}{(n/p)}\big{)}$ time with
$t=O\big{(}p^{2}\min(n,p)\big{)}$ where
$\min(g,h)=\min\\{\log{g},(\log_{h}{g})^{2}\\}$. Therefore, we get
$m=O\big{(}(d-u)^{2}\min(n,d-u+1)\big{)}$ and
$b=O\big{(}u^{2}\min(n,u)\big{)}$. As a result, the number of tests is:

$\displaystyle a+b\times a+m\times b\times a$ (6)
$\displaystyle=O\left(d(d-u)^{2}u^{2}\log{\frac{n}{d}}\times\min(n,d-u+1)\min(n,u)\times\min\left\\{u^{u},(d-u)^{d-u}\right\\}\right)$
$\displaystyle=O\left(d^{3}(\log^{2}{n})\log{\frac{n}{d}}\right),\mbox{ if $u$
is a constant.}$ (7)

The decoding complexity is

$\displaystyle O(a)+O(b\times a)+O(b\times a)\times
O\big{(}(d-u)^{2}\min(n,d-u+1)+(d-u)\log^{2}{\frac{n}{d-u}}\big{)}$
$\displaystyle=O\left(d(d-u)u^{2}\log{\frac{n}{d}}\min(n,u)\min\left\\{u^{u},(d-u)^{d-u}\right\\}\times\left((d-u)\min(n,d-u+1)+\log^{2}{\frac{n}{d-u}}\right)\right).$

####  III-C6 Example

We delineate our encoding and decoding procedures by an example here.

_Encoding:_ Suppose $n=12,d=3,u=2$, and the defective set is $P=\\{1,8,11\\}$.
Matrix $\mathcal{A}$ of size $6\times 12$ is a $(d=3,u=2,n=12)$-single
selector and matrices $\mathcal{B}$ and $\mathcal{M}$ of size $9\times 12$ are
$(d+u-1)=u=2$-disjunct matrices. We get $a=6,m=b=9$. Because the number of
rows in $\mathcal{T}$ is $amb=486$ which is large to be written in this paper,
we only demonstrate some columns and rows of interest here. Matrices
$\mathcal{A},\mathcal{B}$, and $\mathcal{M}$ are given as follows.

$\displaystyle\mathcal{A}$
$\displaystyle=\left[\begin{tabular}[]{cccccccccccc}{0}&1&0&1&0&0&1&{0}&0&0&{0}&1\\\
{1}&0&0&1&0&1&0&{0}&1&1&{0}&0\\\ {1}&0&1&0&1&1&0&{1}&1&1&{1}&0\\\
{0}&1&1&0&1&0&1&{1}&0&0&{1}&1\\\ {1}&1&0&0&1&1&0&{0}&0&0&{1}&1\\\
{0}&0&1&1&0&0&1&{1}&1&1&{0}&0\end{tabular}\right],$ (14)
$\displaystyle\mathcal{B}=\mathcal{M}$
$\displaystyle=\left[\begin{tabular}[]{cccccccccccc}{0}&0&0&0&0&0&1&{1}&1&1&{0}&0\\\
{0}&0&0&1&1&1&0&{0}&0&1&{0}&0\\\ {1}&1&1&0&0&0&0&{0}&0&1&{0}&0\\\
{0}&0&1&0&0&1&0&{0}&1&0&{1}&0\\\ {0}&1&0&0&1&0&0&{1}&0&0&{1}&0\\\
{1}&0&0&1&0&0&1&{0}&0&0&{1}&0\\\ {0}&1&0&1&0&0&0&{0}&1&0&{0}&1\\\
{0}&0&1&0&1&0&1&{0}&0&0&{0}&1\\\
{1}&0&0&0&0&1&0&{1}&0&0&{0}&1\end{tabular}\right].$ (24)

Since $P=\\{1,8,11\\}$, we only consider columns $1,8$, and $11$ in any matrix
considered later. Let us denote $\mathcal{Y}\mid_{P}$ be the pruning matrix of
$\mathcal{Y}$ restricted by the columns whose indices are in $P$. The output
matrices between $\mathcal{B}$ and $\mathcal{A}$ restricted to $P$ by using
the exclusion operator are:

$\displaystyle(\mathcal{B}\circ\mathcal{A}(1,:))\mid_{P}$
$\displaystyle=\left[\begin{tabular}[]{ccc}0&0&0\\\ 0&0&0\\\ 0&0&0\\\ 0&0&0\\\
0&0&0\\\ 0&0&0\\\ 0&0&0\\\ 0&0&0\\\
0&0&0\end{tabular}\right],(\mathcal{B}\circ\mathcal{A}(2,:))\mid_{P}$
$\displaystyle=\left[\begin{tabular}[]{ccc}1&0&0\\\ 1&0&0\\\ 0&0&0\\\ 1&0&0\\\
1&0&0\\\ 0&0&0\\\ 1&0&0\\\ 1&0&0\\\
0&0&0\end{tabular}\right],(\mathcal{B}\circ\mathcal{A}(3,:))\mid_{P}$
$\displaystyle=\left[\begin{tabular}[]{ccc}1&0&1\\\ 1&1&1\\\ 0&1&1\\\ 1&1&0\\\
{1}&{0}&{0}\\\ {0}&{1}&{0}\\\ 1&1&1\\\ 1&1&1\\\
{0}&{0}&{1}\end{tabular}\right],$ (52)
$\displaystyle(\mathcal{B}\circ\mathcal{A}(4,:))\mid_{P}$
$\displaystyle=\left[\begin{tabular}[]{ccc}{0}&{0}&{1}\\\ 0&1&1\\\ 0&1&1\\\
{0}&{1}&{0}\\\ {0}&{0}&{0}\\\ {0}&{1}&{0}\\\ 0&1&1\\\ 0&1&1\\\
{0}&{0}&{1}\end{tabular}\right],(\mathcal{B}\circ\mathcal{A}(5,:))\mid_{P}$
$\displaystyle=\left[\begin{tabular}[]{ccc}1&0&1\\\ 1&0&1\\\ {0}&{0}&{1}\\\
{1}&{0}&{0}\\\ {1}&{0}&{0}\\\ {0}&{0}&{0}\\\ 1&0&1\\\ 1&0&1\\\
{0}&{0}&{1}\end{tabular}\right],(\mathcal{B}\circ\mathcal{A}(6,:))\mid_{P}$
$\displaystyle=\left[\begin{tabular}[]{ccc}0&0&0\\\ 0&1&0\\\ 0&1&0\\\ 0&1&0\\\
0&0&0\\\ 0&1&0\\\ 0&1&0\\\ 0&1&0\\\ 0&0&0\end{tabular}\right]$ (80)

For $u=2$, the test outcomes for matrix $\mathcal{A}$ is
$\mathsf{test}(\mathcal{A}(1,:))=\mathsf{test}(\mathcal{A}(2,:))=\mathsf{test}(\mathcal{A}(6,:))=0,\mathsf{test}(\mathcal{A}(3,:))=\mathsf{test}(\mathcal{A}(4,:))=\mathsf{test}(\mathcal{A}(5,:))=1$.
For the tests on $\mathcal{M}\vee(\mathcal{B}\circ\mathcal{A})$, we only show
the tests of interest as follows.

$\displaystyle\mathsf{test}(\mathcal{B}(5,:)\circ\mathcal{A}(3,:))$
$\displaystyle=0,\mathsf{test}(\mathcal{M}\vee(\mathcal{B}(5,:)\circ\mathcal{A}(3,:)))$
$\displaystyle=[1,0,0,1,1,1,0,0,1]^{T};$
$\displaystyle\mathsf{test}(\mathcal{B}(6,:)\circ\mathcal{A}(3,:))$
$\displaystyle=0,\mathsf{test}(\mathcal{M}\vee(\mathcal{B}(6,:)\circ\mathcal{A}(3,:)))$
$\displaystyle=[0,0,1,1,1,1,0,0,1]^{T};$
$\displaystyle\mathsf{test}(\mathcal{B}(9,:)\circ\mathcal{A}(3,:))$
$\displaystyle=0,\mathsf{test}(\mathcal{M}\vee(\mathcal{B}(9,:)\circ\mathcal{A}(3,:)))$
$\displaystyle=[1,0,1,0,1,1,0,0,1]^{T};$
$\displaystyle\mathsf{test}(\mathcal{B}(1,:)\circ\mathcal{A}(4,:))$
$\displaystyle=0,\mathsf{test}(\mathcal{M}\vee(\mathcal{B}(1,:)\circ\mathcal{A}(4,:)))$
$\displaystyle=[1,0,1,0,1,1,0,0,1]^{T};$
$\displaystyle\mathsf{test}(\mathcal{B}(4,:)\circ\mathcal{A}(4,:))$
$\displaystyle=0,\mathsf{test}(\mathcal{M}\vee(\mathcal{B}(4,:)\circ\mathcal{A}(4,:)))$
$\displaystyle=[0,0,1,1,1,1,0,0,1]^{T};$
$\displaystyle\mathsf{test}(\mathcal{B}(5,:)\circ\mathcal{A}(4,:))$
$\displaystyle=0,\mathsf{test}(\mathcal{M}\vee(\mathcal{B}(5,:)\circ\mathcal{A}(4,:)))$
$\displaystyle=[0,0,0,0,1,1,0,0,1]^{T};$
$\displaystyle\mathsf{test}(\mathcal{B}(6,:)\circ\mathcal{A}(4,:))$
$\displaystyle=0,\mathsf{test}(\mathcal{M}\vee(\mathcal{B}(6,:)\circ\mathcal{A}(4,:)))$
$\displaystyle=[0,0,1,1,1,1,0,0,1]^{T};$
$\displaystyle\mathsf{test}(\mathcal{B}(9,:)\circ\mathcal{A}(4,:))$
$\displaystyle=0,\mathsf{test}(\mathcal{M}\vee(\mathcal{B}(9,:)\circ\mathcal{A}(4,:)))$
$\displaystyle=[1,0,1,0,1,1,0,0,1]^{T};$
$\displaystyle\mathsf{test}(\mathcal{B}(3,:)\circ\mathcal{A}(5,:))$
$\displaystyle=0,\mathsf{test}(\mathcal{M}\vee(\mathcal{B}(3,:)\circ\mathcal{A}(5,:)))$
$\displaystyle=[0,0,1,1,1,1,0,0,1]^{T};$
$\displaystyle\mathsf{test}(\mathcal{B}(4,:)\circ\mathcal{A}(5,:))$
$\displaystyle=0,\mathsf{test}(\mathcal{M}\vee(\mathcal{B}(4,:)\circ\mathcal{A}(5,:)))$
$\displaystyle=[1,0,0,1,1,1,0,0,1]^{T};$
$\displaystyle\mathsf{test}(\mathcal{B}(5,:)\circ\mathcal{A}(5,:))$
$\displaystyle=0,\mathsf{test}(\mathcal{M}\vee(\mathcal{B}(5,:)\circ\mathcal{A}(5,:)))$
$\displaystyle=[1,0,0,1,1,1,0,0,1]^{T};$
$\displaystyle\mathsf{test}(\mathcal{B}(6,:)\circ\mathcal{A}(5,:))$
$\displaystyle=0,\mathsf{test}(\mathcal{M}\vee(\mathcal{B}(6,:)\circ\mathcal{A}(5,:)))$
$\displaystyle=[0,0,0,0,1,1,0,0,1]^{T};$
$\displaystyle\mathsf{test}(\mathcal{B}(9,:)\circ\mathcal{A}(5,:))$
$\displaystyle=0,\mathsf{test}(\mathcal{M}\vee(\mathcal{B}(9,:)\circ\mathcal{A}(5,:)))$
$\displaystyle=[0,0,1,1,1,1,0,0,1]^{T}.$

_Decoding:_ Set $P=\emptyset$. For $i=1,2,6$, we get
$\mathsf{test}(\mathcal{A}(1,:))=\mathsf{test}(\mathcal{A}(2,:))=\mathsf{test}(\mathcal{A}(6,:))=0$.
Therefore, we do not proceed to decode the test outcomes generated by rows
$\mathcal{A}(1,:),\mathcal{A}(2,:)$, and $\mathcal{A}(6,:)$. From now, we
examine rows $\mathcal{A}(3,:),\mathcal{A}(4,:)$, and $\mathcal{A}(5,:)$.
Consider row $\mathcal{A}(3,:)$. Because
$\mathsf{test}(\mathcal{B}(1,:)\circ\mathcal{A}(3,:))=\mathsf{test}(\mathcal{B}(2,:)\circ\mathcal{A}(3,:))=\mathsf{test}(\mathcal{B}(3,:)\circ\mathcal{A}(3,:))=\mathsf{test}(\mathcal{B}(4,:)\circ\mathcal{A}(3,:))=\mathsf{test}(\mathcal{B}(7,:)\circ\mathcal{A}(3,:))=\mathsf{test}(\mathcal{B}(8,:)\circ\mathcal{A}(3,:))=1$,
we only consider
$\mathsf{test}(\mathcal{B}(5,:)\circ\mathcal{A}(3,:))=\mathsf{test}(\mathcal{B}(6,:)\circ\mathcal{A}(3,:))=\mathsf{test}(\mathcal{B}(9,:)\circ\mathcal{A}(3,:))=0$.
We get
$S_{5,3}=\mathrm{dec}(\mathsf{test}(\mathcal{M}\vee(\mathcal{B}(5,:)\circ\mathcal{A}(3,:))),\mathcal{M})=\\{8,11\\}$,
$S_{6,3}=\mathrm{dec}(\mathsf{test}(\mathcal{M}\vee(\mathcal{B}(6,:)\circ\mathcal{A}(3,:))),\mathcal{M})=\\{1,11\\}$,
and
$S_{9,3}=\mathrm{dec}(\mathsf{test}(\mathcal{M}\vee(\mathcal{B}(9,:)\circ\mathcal{A}(3,:))),\mathcal{M})=\\{1,8\\}$.
The defective set after processing row $\mathcal{A}(3,:)$ and the tests
generated by it is $P=P\cup S_{5,3}\cup S_{6,3}\cup S_{9,3}=\\{1,8,11\\}$.

Similarly, for row $\mathcal{A}(4,:)$, we only consider
$\mathsf{test}(\mathcal{B}(1,:)\circ\mathcal{A}(4,:))=\mathsf{test}(\mathcal{B}(4,:)\circ\mathcal{A}(4,:))=\mathsf{test}(\mathcal{B}(5,:)\circ\mathcal{A}(4,:))=\mathsf{test}(\mathcal{B}(6,:)\circ\mathcal{A}(4,:))=\mathsf{test}(\mathcal{B}(9,:)\circ\mathcal{A}(4,:))=0$.
Then we get
$S_{1,4}=\\{1,8\\},S_{4,4}=\\{1,11\\},S_{5,4}=\emptyset,S_{6,4}=\\{1,11\\},S_{9,4}=\\{1,8\\}$.
The defective set after processing row $\mathcal{A}(4,:)$ and the tests
generated by it is $P=P\cup S_{1,4}\cup S_{4,4}\cup S_{5,4}\cup S_{6,4}\cup
S_{9,4}=\\{1,8,11\\}\cup\\{1,8\\}\cup\\{1,11\\}\cup\emptyset\cup\\{1,11\\}\cup\\{1,8\\}=\\{1,8,11\\}$.
For row $\mathcal{A}(5,:)$, we only consider
$\mathsf{test}(\mathcal{B}(3,:)\circ\mathcal{A}(5,:))=\mathsf{test}(\mathcal{B}(4,:)\circ\mathcal{A}(5,:))=\mathsf{test}(\mathcal{B}(5,:)\circ\mathcal{A}(5,:))=\mathsf{test}(\mathcal{B}(6,:)\circ\mathcal{A}(5,:))=\mathsf{test}(\mathcal{B}(9,:)\circ\mathcal{A}(5,:))=0$.
And therefore, we get
$S_{3,5}=\\{1,8\\},S_{4,5}=\\{8,11\\},S_{5,5}=\\{8,11\\},S_{6,5}=\emptyset,S_{9,5}=\\{1,8\\}$.
Consequently, the defective set after processing row $\mathcal{A}(5,:)$ and
the tests generated by it is $P=P\cup S_{3,5}\cup S_{4,5}\cup S_{5,5}\cup
S_{6,5}\cup S_{9,5}=\\{1,8,11\\}$. This is also the final defective set.

##  IV Non-adaptive and 2-stage designs for $u=2$

In this section, we present designs with decoding time of
$O(d^{2}\log^{2}{(n/d)})$ to find the defective set for
$(n,d,\ell=1,u=2)$-TGT. When $u=2$, we only need two rows in which each row
contains exactly one defective item and the two defective items in the two
rows are distinct. This idea was proposed in [29] for a randomized and non-
adaptive design. Since our designs are deterministic, the technical details
are different from theirs. We first present the notion of selectors which will
be used for our designs later.

###  IV-A Selectors

To have an efficient decoding procedure, we recall a tool named _selectors_
which were introduced by De Bonis et al. [13].

######  Definition 3.

[13] Given integers $k$, $m$, and $n$, with $1\leq m\leq k\leq n$, we say that
a Boolean matrix M with $t$ rows and $n$ columns is a $(k,m,n)$-selector if
any submatrix of $\mathcal{M}$ obtained by choosing $k$ out of $n$ arbitrary
columns of $\mathcal{M}$ contains at least $m$ distinct rows of the identity
matrix $\mathcal{I}_{k}$. The integer $t$ is the size of the
$(k,m,n)$-selector.

######  Theorem 5.

[13, Theorem 1] Given integers $1\leq m\leq k\leq n$, there exists a
$(k,m,n)$-selector of size $t$, with

$t<\frac{\mathrm{e}k^{2}}{k-m+1}\log{\frac{n}{k}}+\frac{\mathrm{e}k(2k-1)}{k-m+1}.$

###  IV-B Main idea

Our main idea consists of two parts:

  * •

Use a $(2d,d+2,n)$-selector to obtain at least two indicating subsets in which
each contains only one defective item and non-defective items.

  * •

For each indicating subset, add it to every test in SGT to find the defective
items. In particular, a test is positive if at least one more defective item
is present and negative otherwise. Hence, the standard group testing
techniques can be applied to find the defective items.

We present the results of non-adaptive and 2-stage designs in Theorem 2 and
their details in the subsequent sections. Note that the proofs of their
complexities are presented in the full version.

###  IV-C Non-adaptive design

Encoding: We first initialize a $(2d,d+2,n)$-selector $\mathcal{A}$ of size
$a\times n$ and an $m\times n$ $d$-disjunct matrix $\mathcal{M}$. Then we
generate three types of vectors: indicator vector
$\mathbf{y}:=\mathsf{test}(\mathcal{A})$, reference vector
$\mathbf{r}:=\mathsf{test}(\mathcal{A}\vee\mathcal{A})$, and identification
vector $\mathbf{f}:=\mathsf{test}(\mathcal{M}\vee\mathcal{A})$. The indicator
and reference vectors are used to locate two tests such that they contain two
distinct defective items and each contains only one defective item. The
identification vector is then to recover the defective set based on these two
tests.

Decoding: We first find two indices $i_{1}\neq i_{2}\in[a]$ by scanning the
indicator vector $\mathbf{y}$ and the reference vector $\mathbf{r}$ such that
$\mathsf{test}(\mathcal{A}(i_{1},:))=\mathsf{test}(\mathcal{A}(i_{2},:))=0$
and $\mathsf{test}(\mathcal{A}(i_{1},:)\vee\mathcal{A}(i_{2},:))=1$. Then the
defective set is
$P=\mathrm{dec}(\mathsf{test}(\mathcal{M}\vee\mathcal{A}(i_{1},:)),\mathcal{M})\cup\mathrm{dec}(\mathsf{test}(\mathcal{M}\vee\mathcal{A}(i_{2},:)),\mathcal{M})$.

Correctness: Consider an arbitrary set $C\subset[n]$ with $C\cap P=P$ and
$|C|=2d$. From Definition 3, since $\mathcal{A}$ is a $(2d,d+2,n)$-selector,
there exists at least $d+2$ distinct rows of the identity matrix
$\mathcal{I}_{2d}$. Because $|P|=d\geq 2$, there must exist two rows $i_{1}$
and $i_{2}$ in $\mathcal{A}$ such that two distinct defective items belong to
them and each row contains a single defective item. In other words,
$\mathsf{supp}(\mathcal{A}(i_{1},:))\cap P=\\{p_{1}\\}$ and
$\mathsf{supp}(\mathcal{A}(i_{2},:))\cap P=\\{p_{2}\\}$ for $p_{1}\neq
p_{2}\in P$. Because
$\mathsf{test}(\mathcal{A}(i_{1},:))=\mathsf{test}(\mathcal{A}(i_{2},:))=0$,
by Lemma 2, we get
$\mathrm{dec}(\mathsf{test}(\mathcal{M}\vee\mathcal{A}(i_{1},:)),\mathcal{M})=P\setminus\\{p_{1}\\}$
and
$\mathrm{dec}(\mathsf{test}(\mathcal{M}\vee\mathcal{A}(i_{2},:)),\mathcal{M})=P\setminus\\{p_{2}\\}$.
Therefore, we always get $P\subseteq S$.

Now we prove that $S$ never contains false defective items. Indeed, because we
only process row $i$ with $\mathsf{test}(\mathcal{A}(i,:))=0$, row
$\mathcal{A}(i,:)$ satisfies $|\mathsf{supp}(\mathcal{A}(i,:))\cap P|\leq
u-1=1$. Therefore, by Lemma 2, the procedure
$\mathrm{dec}(\mathsf{test}(\mathcal{M}\vee\mathcal{A}(i,:)),\mathcal{M})$
either return to a set of defective items or an empty set. Set $S$ thus never
contains false defective items.

Complexity: By using the result in Theorem 5, the number of tests in
$\mathcal{A}$ is $a=O\big{(}d\log{\frac{n}{d}}\big{)}$. By Theorem 3, an
$m\times n$ $d$-disjunct matrix $\mathcal{M}$ can be efficiently decoded in
$O\big{(}m+d\log^{2}{(n/d)}\big{)}$ time with
$m=O\big{(}d^{2}\min(n,d)\big{)}$. Therefore, the number of tests the non-
adaptive design is:

$\displaystyle a+a^{2}+am=O\left(d^{3}\log{\frac{n}{d}}\cdot\min(n,d)\right).$

To identify $i_{1}$ and $i_{2}$, it takes
$O(a^{2})=O\big{(}d^{2}\log^{2}{\frac{n}{d}}\big{)}$ time. Because of the
construction of $\mathcal{M}$, it takes
$2O\big{(}d^{2}\min\\{\log{n},(\log_{d}{n})^{2}\\}+d\log^{2}{(n/d)}\big{)}$
time to run
$\mathrm{dec}(\mathsf{test}(\mathcal{M}\vee\mathcal{A}(i_{1},:)),\mathcal{M})$
and
$\mathrm{dec}(\mathsf{test}(\mathcal{M}\vee\mathcal{A}(i_{2},:)),\mathcal{M})$.
Therefore, it takes
$O\left(d^{2}\left(\log^{2}{\frac{n}{d}}+\min(n,d)\right)\right)$ time to run
the non-adaptive design.

###  IV-D 2-stage design

Encoding and decoding: In the first stage, we utilize matrices
$\mathcal{A},\mathcal{M}$, the indicator vector $\mathbf{y}$, the reference
vector $\mathbf{r}$ in Section IV-C. However, we amend vector $\mathbf{f}$ as
follows. We initialize a $(d,d,n)$-list disjunct matrix $\mathcal{H}$ of size
$h\times n$ as in Theorem 4 which can be decoded in
$O\big{(}d\log^{2}{(n/d)}\big{)}$ time with $h=O\big{(}d\log{(n/d)}\big{)}$.
Then we set $\mathbf{f}=\mathsf{test}(\mathcal{H}\vee\mathcal{A})$.

In the second stage, we first find two indices $i_{1}\neq i_{2}\in[a]$ by
scanning the indicator vector $\mathbf{y}$ and $\mathbf{r}$ such that
$\mathsf{test}(\mathcal{A}(i_{1},:))=\mathsf{test}(\mathcal{A}(i_{2},:))=0$
and $\mathsf{test}(\mathcal{A}(i_{1},:)\vee\mathcal{A}(i_{2},:))=1$. Then the
approximate defective set is
$R=\mathrm{dec}(\mathsf{test}(\mathcal{H}\vee\mathcal{A}(i_{1},:)),\mathcal{H})\cup\mathrm{dec}(\mathsf{test}(\mathcal{H}\vee\mathcal{A}(i_{2},:)),\mathcal{H})$.
Finally, we test every two items in $R$. If a test on two items is positive
then we add them to the defective set.

Correctness: Similar to the analysis in Section IV-C, when
$\mathsf{test}(\mathcal{A}(i_{1},:))=\mathsf{test}(\mathcal{A}(i_{2},:))=0$
and $\mathsf{test}(\mathcal{A}(i_{1},:)\vee\mathcal{A}(i_{2},:))=1$, we get
$|\mathcal{A}(i_{1},:)\cap P|=1$ and $|\mathcal{A}(i_{2},:)\cap P|=1$. Let
$\\{p_{1}\\}=\mathcal{A}(i_{1},:)\cap P$ and
$\\{p_{2}\\}=\mathcal{A}(i_{2},:)\cap P$. It is straightforward that
$p_{1}\neq p_{2}$.

When $|\mathsf{supp}(\mathbf{x})\cap P|=u-1$, it is easy to confirm that
$\mathcal{T}\otimes\mathbf{x}=\mathcal{T}\odot\mathsf{vecc}(P\setminus(\mathsf{supp}(\mathbf{x})\cap
P))$ for any matrix $\mathcal{T}$. Therefore, we have
$\mathsf{test}(\mathcal{H}\vee\mathcal{A}(i_{1},:))=\mathcal{H}\odot\mathsf{vecc}(P\setminus(\mathcal{A}(i_{1},:)\cap
P))=\mathcal{H}\odot\mathsf{vecc}(P\setminus\\{p_{1}\\})$ and
$\mathsf{test}(\mathcal{H}\vee\mathcal{A}(i_{2},:))=\mathcal{H}\odot\mathsf{vecc}(P\setminus(\mathcal{A}(i_{2},:)\cap
P))=\mathcal{H}\odot\mathsf{vecc}(P\setminus\\{p_{2}\\})$. Since $\mathcal{H}$
is a $(d,d)$-list disjunct matrix, we get
$\mathrm{dec}(\mathsf{test}(\mathcal{H}\vee\mathcal{A}(i_{k},:)),\mathcal{H})=P\setminus\\{p_{k}\\}$
and
$|\mathrm{dec}(\mathsf{test}(\mathcal{H}\vee\mathcal{A}(i_{k},:)),\mathcal{H})|\leq
2d-1$ for $k=1,2$. Therefore, $|R|\leq 3d-2$. Since we are considering the
case without gap with $u=2$, if a test on two items is positive, the two items
must be defective. On the other hand, since $R\cap P=P$, all pairs of the
defective items will be tested, and therefore, by adding every two items in a
test that yields a positive outcome will recover the defective set.

Complexity: The number of tests is:

$\displaystyle a+a^{2}+ah+{|R|\choose
2}=O\left(d^{2}\log^{2}{\frac{n}{d}}\right).$

In the second stage, to identify $i_{1}$ and $i_{2}$, it takes
$O(a^{2})=O\big{(}d^{2}\log^{2}{\frac{n}{d}}\big{)}$ time. Because of the
construction of $\mathcal{H}$, it takes $O\big{(}d\log^{2}{(n/d)}\big{)}$ time
to decode
$\mathrm{dec}(\mathsf{test}(\mathcal{H}\vee\mathcal{A}(i_{1},:)),\mathcal{H})$
and
$\mathrm{dec}(\mathsf{test}(\mathcal{H}\vee\mathcal{A}(i_{2},:)),\mathcal{H})$.
Finally, it takes $O\big{(}{|R|\choose 2}\big{)}=O({3d-2\choose 2})=O(d^{2})$
time to get the defective set $P$. In summary, it takes
$O\big{(}d^{2}\log^{2}{\frac{n}{d}}\big{)}+O\big{(}d\log^{2}{(n/d)}\big{)}+O(d^{2})=O\big{(}d^{2}\log^{2}{\frac{n}{d}}\big{)}$
time to run the 2-stage design.

##  V Conclusion

In this paper, we first present efficient decoding designs with a polynomial
time of $\min\\{u^{u},(d-u)^{d-u}\\},d$, and $\log{n}$ for TGT without gap
under the deterministic design, the combinatorial setting, and the exact
recovery criterion. It is inciting to extend this work for the case TGT with a
gap. Another interesting question is whether the designs here are applicable
to find hidden graphs in learning theory.

## References

  * [1] R. Dorfman, “The detection of defective members of large populations,” The Annals of mathematical statistics, vol. 14, no. 4, pp. 436–440, 1943.
  * [2] D. M. Malioutov, K. R. Varshney, A. Emad, and S. Dash, “Learning interpretable classification rules with Boolean compressed sensing,” Transparent Data Mining for Big and Small Data, pp. 95–121, 2017.
  * [3] I. Shin, Y. Shen, Y. Xuan, M. T. Thai, and T. Znati, “Reactive jamming attacks in multi-radio wireless sensor networks: An efficient mitigating measure by identifying trigger nodes,” in ACM International Workshop on Foundations of Wireless ad hoc and Sensor Networking and Computing, pp. 87–96, 2009.
  * [4] P. Damaschke, “Threshold group testing,” in General theory of information transfer and combinatorics, pp. 707–718, Springer, 2006.
  * [5] N. Shental, S. Levy, V. Wuvshet, S. Skorniakov, B. Shalem, A. Ottolenghi, Y. Greenshpan, R. Steinberg, A. Edri, R. Gillis, et al., “Efficient high-throughput SARS-CoV-2 testing to detect asymptomatic carriers,” Science advances, vol. 6, no. 37, p. eabc5961, 2020.
  * [6] D. Du, F. K. Hwang, and F. Hwang, Combinatorial group testing and its applications, vol. 12.  World Scientific, 2000.
  * [7] A. D’yachkov, N. Polyanskii, V. Shchukin, and I. Vorobyev, “Separable codes for the symmetric multiple-access channel,” IEEE Transactions on Information Theory, vol. 65, no. 6, pp. 3738–3750, 2019.
  * [8] A. D’yachkov, V. Rykov, C. Deppe, and V. Lebedev, “Superimposed codes and threshold group testing,” Information Theory, Combinatorics, and Search Theory: In Memory of Rudolf Ahlswede, pp. 509–533, 2013.
  * [9] M. Cheraghchi, “Improved constructions for non-adaptive threshold group testing,” Algorithmica, vol. 67, no. 3, pp. 384–417, 2013.
  * [10] H.-B. Chen and H.-L. Fu, “Nonadaptive algorithms for threshold group testing,” Discrete Applied Mathematics, vol. 157, no. 7, pp. 1581–1585, 2009.
  * [11] T. V. Bui, M. Kuribayashi, M. Cheraghchi, and I. Echizen, “Efficiently decodable non-adaptive threshold group testing,” IEEE Transactions on Information Theory, vol. 65, no. 9, pp. 5519–5528, 2019.
  * [12] G. De Marco, T. Jurdziński, D. R. Kowalski, M. Różański, and G. Stachowiak, “Subquadratic non-adaptive threshold group testing,” Journal of Computer and System Sciences, vol. 111, pp. 42–56, 2020.
  * [13] A. De Bonis, L. Gasieniec, and U. Vaccaro, “Optimal two-stage algorithms for group testing problems,” SIAM Journal on Computing, vol. 34, no. 5, pp. 1253–1270, 2005.
  * [14] A. G. D’yachkov and V. V. Rykov, “Bounds on the length of disjunctive codes,” Problemy Peredachi Informatsii, vol. 18, no. 3, pp. 7–13, 1982.
  * [15] E. Porat and A. Rothschild, “Explicit nonadaptive combinatorial group testing schemes,” IEEE Transactions on Information Theory, vol. 57, no. 12, pp. 7982–7989, 2011.
  * [16] P. Indyk, H. Q. Ngo, and A. Rudra, “Efficiently decodable non-adaptive group testing,” in ACM-SIAM Symposium on Discrete Algorithms, pp. 1126–1142, SIAM, 2010.
  * [17] H. Q. Ngo, E. Porat, and A. Rudra, “Efficiently decodable error-correcting list disjunct matrices and applications - (extended abstract),” in Automata, Languages and Programming - 38th International Colloquium, ICALP 2011, Zurich, Switzerland, July 4-8, 2011, Proceedings, Part I (L. Aceto, M. Henzinger, and J. Sgall, eds.), vol. 6755 of Lecture Notes in Computer Science, pp. 557–568, Springer, 2011.
  * [18] M. Cheraghchi and V. Nakos, “Combinatorial group testing and sparse recovery schemes with near-optimal decoding time,” in 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), pp. 1203–1213, IEEE, 2020\.
  * [19] S. Cai, M. Jahangoshahi, M. Bakshi, and S. Jaggi, “Efficient algorithms for noisy group testing,” IEEE Trans. Inf. Theory, vol. 63, no. 4, pp. 2113–2136, 2017.
  * [20] S. Bondorf, B. Chen, J. Scarlett, H. Yu, and Y. Zhao, “Sublinear-time non-adaptive group testing with $o(k\log{n})$ tests via bit-mixing coding,” IEEE Transactions on Information Theory, vol. 67, no. 3, pp. 1559–1570, 2020.
  * [21] C. L. Chan, S. Cai, M. Bakshi, S. Jaggi, and V. Saligrama, “Stochastic threshold group testing,” in 2013 IEEE Information Theory Workshop (ITW), pp. 1–5, IEEE, 2013.
  * [22] A. Reisizadeh, P. Abdalla, and R. Pedarsani, “Sub-linear time stochastic threshold group testing via sparse-graph codes,” in 2018 IEEE Information Theory Workshop (ITW), pp. 1–5, IEEE, 2018.
  * [23] W. Kautz and R. Singleton, “Nonrandom binary superimposed codes,” IEEE Transactions on Information Theory, vol. 10, no. 4, pp. 363–377, 1964.
  * [24] D. R. Stinson and R. Wei, “Generalized cover-free families,” Discrete Mathematics, vol. 279, no. 1-3, pp. 463–477, 2004.
  * [25] A. D’yachkov, P. Vilenkin, D. Torney, and A. Macula, “Families of finite sets in which no intersection of $\ell$ sets is covered by the union of $s$ others,” Journal of Combinatorial Theory, Series A, vol. 99, no. 2, pp. 195–218, 2002.
  * [26] A. G. Dyachkov and V. V. Rykov, “A survey of superimposed code theory,” Problems of Control and Information Theory, vol. 12, no. 4, pp. 1–13, 1983.
  * [27] A. Rashad, “Random coding bounds on the rate for list-decoding superimposed codes,” PROBLEMS OF CONTROL AND INFORMATION THEORY-PROBLEMY UPRAVLENIYA I TEORII INFORMATSII, vol. 19, no. 2, pp. 141–149, 1990.
  * [28] M. Cheraghchi, “Noise-resilient group testing: Limitations and constructions,” Discrete Applied Mathematics, vol. 161, no. 1-2, pp. 81–95, 2013.
  * [29] T. V. Bui and J. Scarlett, “Concomitant group testing,” IEEE Transactions on Information Theory, pp. –, 2024.

##  Appendix A Proof of Lemma 2

Consider
$y_{i}=\mathsf{test}(\mathcal{M}(i,:)\vee\mathbf{x})=\mathsf{test}(\mathsf{supp}(\mathcal{M}(i,:))\cup\mathsf{supp}(\mathbf{x}))$
for $i=1,\ldots,t$. Since $\mathcal{M}$ is a $p$-disjunct matrix, For every
defective item $r\in P$, there exists a row $i_{r}$, called _a private row_ ,
such that that row contains $r$ and does not contain the remaining items in
$P\setminus\\{r\\}$. Therefore, if $|\mathsf{supp}(\mathbf{x})\cap P|<u-1$,
$y_{i_{r}}=0$. Consequently, any decoding procedure with the exact recovery in
standard group testing with the measurement matrix $\mathcal{M}$ must declare
item $r$ as non-defective. Therefore, the decoding procedure returns an empty
set.

When $|\mathsf{supp}(\mathbf{x})\cap P|=u-1$, for any
$r\in\mathsf{supp}(\mathbf{x})\cap P$, we get $y_{i_{r}}=0$ because row
$i_{r}$ contains only $u-1$ defective items in $\mathsf{supp}(\mathbf{x})\cap
P$. Therefore, any item in $\mathsf{supp}(\mathbf{x})\cap P$ will not be
included in the returned defective set by any decoding procedure with the
exact recovery in standard group testing. On the other hand, for any
$r^{\prime}\in P\setminus\mathsf{supp}(\mathbf{x})$, every test that includes
$r^{\prime}$ is positive. Because $\mathcal{M}$ is a $p$-disjunct matrix, item
$i^{\prime}$ will be included in the returned defective set by any decoding
procedure with the exact recovery in standard group testing. In other words,
the returned defective set is $P\setminus\mathsf{supp}(\mathbf{x})$ if
$|\mathsf{supp}(\mathbf{x})\cap P|=u-1$.