Efficiently Decodable Non-Adaptive Threshold
Group Testing
Thach V. Bui∗ , Minoru Kuribayashi‡ , Mahdi Cheraghchi§, and Isao Echizen∗†

arXiv:1712.07509v3 [] 30 Jan 2018

∗ SOKENDAI

(The
Graduate University
for Advanced
Studies), Hayama,
Kanagawa, Japan
bvthach@nii.ac.jp

‡ Graduate

§ Department of
† National Institute
School
of Natural Science
Computing, Imperial
of Informatics,
and Technology,
College London, UK
Tokyo, Japan
Okayama University,
m.cheraghchi@imperial.ac.uk iechizen@nii.ac.jp
Okayama, Japan
kminoru@okayama-u.ac.jp

Abstract
We consider non-adaptive threshold group testing for identification of up to d defective items in a set of
N items, where a test is positive if it contains
least
and negative
otherwise. The
 2 ≤uu ≤ d defective items,

 at
 2
2
1
d
+
log
u
log
·
d
log
N
tests
with
probability
defective items can be identified using t = O d2d−u2 e(d−u)
u
ǫ
u u

 2 

· d log Nd + u log ud · d2 log N tests with probability 1.
at least 1 − ǫ for any ǫ > 0 or t = O d2d−u2 e(d−u)
u
t
The decoding time is O(d2 log N ) × poly(d2 log N ). This result significantly improves the best known results for
decoding non-adaptive threshold group testing: O(N log N + N log 1ǫ ) for probabilistic decoding, where ǫ > 0, and
O(N u log N ) for deterministic decoding.

I. I NTRODUCTION
The goal of combinatorial group testing is to identify at most d defective items among a population of
N items (usually d is much smaller than N). This problem dates back to the work of Dorfman [1], who
proposed using a pooling strategy to identify defectives in a collection of blood samples. In each test, a
group of items are pooled, and the combination is tested. The result is positive if at least one item in the
group is defective and is otherwise negative. Damaschke [2] introduced a generalization of classical group
testing known as threshold group testing. In this variation, the result is positive if the corresponding group
contains at least u defective items, where u is a parameter, is negative if the group contains no more than
ℓ defective items, where 0 ≤ ℓ < u, and is arbitrary otherwise. When u = 1 and ℓ = 0, threshold group
testing reduces to classical group testing. We note that ℓ is always smaller than the number of defective
items. Otherwise, every test yields a negative outcome, then no information is enhanced from tests.
There are two approaches for the design of tests. The first is adaptive group testing in which there are
several testing stages, and the design of each stage depends on the outcomes of the previous stages. The
second is non-adaptive group testing (NAGT) in which all tests are designed in advance, and the tests are
performed in parallel. NAGT is appealing to researchers in most application areas, such as computational
and molecular biology [3], multiple access communications [4] and data steaming [5] (cf. [6]). The focus
of this work is on NAGT.
In both threshold and classical group testing, it is desirable to minimize the number of tests and,
to efficiently identify the set of defective items (i.e., have an efficient decoding algorithm). For both
testings, one needs Ω(d log N) tests to identify all defective items [6], [7], [8] using adaptive schemes. In
adaptive schemes, the decoding algorithm is usually implicit in the test design. The number of tests and
the decoding time are significantly different between classical non-adaptive (CNAGT) and non-adaptive
threshold group testing (NATGT).

1

In CNAGT, Porat and Rothschild [9] first proposed explicit nonadaptive constructions using O(d2 log N)
tests. However, there is no efficient (sublinear-time) decoding algorithm associated with their schemes. For
exact identification, there are explicit schemes allowing defective items be identified using poly(d, log N)
tests in time poly(d, log N) [10], [11] (the number of tests can be as low as O(d1+o(1) log N) if false
positives are allowed in the reconstruction). To achieve a nearly optimal number of tests in adaptive group
testing and with low decoding complexity, Cai et al. [12] proposed using probabilistic schemes that need
O(d log d · log N) tests to find the defective items in time O(d(log N + log2 d)).
In
 threshold group testing, Damaschke [2] showed that the set of positive items can be identified with
N
tests with up to g false positives and g false negatives, where g = u − ℓ − 1 is the gap parameter.
u
Cheraghchi [13] showed that it is possible to find the defective items with O(dg+2 log d · log(N/d)) tests,
and that this trade-off is essentially optimal. Recently, De Marco et al. [14] improved this bound to
O(d3/2 log(N/d)) tests under the extra assumption that the number of defective items is exactly d, which
is rather restrictive in application. Although the number of tests has been extensively studied, there have
been few reports that focus on the decoding algorithm as well. Chen andFu [15] proposed schemes
 based

d−u
d u
d
N
on CNAGT for when g = 0 that can find the defective items using O u
d log d tests in
d−u

√
1
u
time O(N log N). Chan et al. [16] presented a randomized algorithm with O log ǫ · d u log N tests to
find the defective items in time O(N log N + N log 1ǫ ) given that g = 0 and u = o(d). The cost of these
decoding schemes increases with N. Our objective is to find an efficient decoding scheme to identify at
most d defective items in NATGT when g = 0.
Contributions: In this paper, we consider the case where g = 0, i.e., ℓ = u − 1 (u ≥ 2), and call
this model u-NATGT. We first propose an efficient scheme for identifying at most d defective items in
t
NATGT in time O(d2 log
× poly(d2 log N), where t is the number of tests. Our main idea is to create at
N)
least a specified number of rows in the test matrix such that the corresponding test in each row contains
exactly u defective items and such that the defective items in the rows are the defective items to be
identified. We “map” these rows using a special matrix constructed from a disjunct matrix (defined later)
and its complementary matrix, thereby converting the outcome in NATGT to the outcome in CNAGT.
The defective items in each row can then be efficiently identified.
Although Cheraghchi [13] and De Marco et al. [14] proposed nearly optimal bounds on the number of
tests, there are no decoding algorithms associated with their schemes. On the other hand, the scheme of
Chen et al. [15] requires an exponential number of tests, which are much larger than the number of tests
in our scheme. Moreover, the decoding complexity of their scheme is exponential in the number of items
N, which is impractical. Chan et al. [16] proposed a probabilistic approach to achieve a small number
of tests, which combinatorially can be better than our scheme. However, their scheme is only applicable
when threshold u is much smaller than d (u = o(d)) and the decoding complexity remains high, namely
O(N log N + N log 1ǫ ), where ǫ > 0 is the precision parameter.
We present a divide and conquer scheme which we then instantiate via deterministic and randomized
decoding. Deterministic decoding is a deterministic scheme in which all defective items can be found
with probability 1. Randomized decoding reduces the number of tests; all defective items can be found
t
× poly(d2 log N). A
with probability at least 1 − ǫ for any ǫ > 0. The decoding complexity is O(d2 log
N)
comparison with existing work is given in Table I.
II. P RELIMINARIES
For consistency, we use capital calligraphic letters for matrices, non-capital letters for scalars, and bold
letters for vectors. All matrix and vector entries are binary. Here are some of the notations used:
1) N, d, x = (x1 , . . . , xN )T : number of items, maximum number of defective items, and binary representation of N items.
2) S = {j1 , j2 , . . . , j|S| }: the set of defective items; cardinality of S is |S| ≤ d.
2

TABLE I
C OMPARISON WITH EXISTING WORK .

Cheraghchi [13]
De Marco et al. [14]
Chen et al. [15]
Chan et al. [16]
Deterministic decoding
Randomized decoding

Number of tests (t)
O(d2 log d · log Nd ) 

q
O d2 · d−u
· log Nd
du




d−u

N
d
d u
d
log
O
u
d−u
d

√
1
O
log
u
log
N
·
d
u ǫ
 2 


· d log N
O d2d−u2 e(d−u)
+ u log ud · d2 log N
u
d
 2 
u

 2
d
1
O d2d−u2 e(d−u)
u
log
+
log
·
d
log
N
u
u
ǫ

Decoding complexity
×

Decoding type
×

×

×

O(N u log N )
O(N log N + N log
t
O(d2 log N)
t
O(d2 log N)

Deterministic
1
)
ǫ

Random

2

× poly(d log N )

Deterministic

2

× poly(d log N )

Random

3) ⊗, ⊙: operation related to u-NATGT and CNAGT, to be defined later.
4) T : t × N measurement matrix used to identify at most d defective items in u-NATGT, where integer
t ≥ 1 is the number of tests.
5) G = (gij ): h × N matrix, where h ≥ 1.
6) M = (mij ): a k × N (d + 1)-disjunct matrix used to identify at most u defective items in u-NATGT
and (d + 1) defective items in CNAGT, where integer k ≥ 1 is the number of tests.
7) M = (mij ): the k × N complementary matrix of M; mij = 1 − mij .
8) Ti,∗ , Gi,∗ , Mi,∗, Mj : row i of matrix T , row i of matrix G, row i of matrix M, and column j of
matrix M, respectively.
9) xi = (xi1 , . . . , xiN )T , Si : binary representation of items and set of indices of defective items in row
Gi,∗ .
10) diag(Gi,∗ ) = diag(gi1 , . . . , giN ): diagonal matrix constructed by input vector Gi,∗ .
A. Problem definition
We index the population of N items from 1 to N. Let [N] = {1, 2, . . . , N} and S be the defective set,
where |S| ≤ d. A test is defined by a subset of items P ⊆ [N]. (d, u, N)-NATGT is a problem in which
there are at most d defective items among N items. A test consisting of a subset of N items is positive
if there are at least u defective items in the test, and each test is designed in advance. Formally, the test
outcome is positive if |P ∩ S| ≥ u and negative if |P ∩ S| < u.
We can model (d, u, N)-NATGT as follows: A t×N binary matrix T = (tij ) is defined as a measurement
matrix, where N is the number of items and t is the number of tests. x = (x1 , . . . , xN )T is the binary
representation vector of N items, where |x| ≤ d. xj = 1 indicates that item j is defective, and xj = 0
indicates otherwise. The jth item corresponds to the jth column of the matrix. An entry tij = 1 naturally
means that item j belongs to test i, and tij = 0 means otherwise. The outcome of all tests is y =
(y1 , . . . , yt )T , where yi = 1 if test i is positive and yi = 0 otherwise. The procedure to get the outcome
vector y is called the encoding procedure. The procedure used to identify defective items from y is called
the decoding procedure. Outcome vector y is

  
T1,∗ ⊗ x
y1
def
def
.

 =  ... 
..
y =T ⊗x=
(1)
Tt,∗ ⊗ x
yt
P
where ⊗ is a notation for the test operation in u-NATGT; namely, yi = Ti,∗ ⊗ x = 1 if N
j=1 xj tij ≥ u,
PN
and yi = Ti,∗ ⊗ x = 0 if j=1 xj tij < u for i = 1, . . . , t. Our objective is to find an efficient decoding
scheme to identify at most d defective items in (d, u, N)-NATGT.
3

B. Disjunct matrices
When u = 1, u-NATGT reduces to CNAGT. To distinguish CNAGT and u-NATGT, we change notation
⊗ to ⊙ and use a k × N measurement matrix M instead of the t × N matrix T . The outcome vector y
in ((1)) is equal to


 
  WN
M1,∗ ⊙ x
y1
N
j=1 xj ∧ m1j
_
def
def
def 

.
.



.
.
y=M⊙x=
Mj = ... 
=
(2)
=
.
.
WN
j=1,x
=1
j
Mk,∗ ⊙ x
yk
j=1 xj ∧ mkj
where ⊙ is the Boolean operator for vector multiplication in which multiplication is replaced
with the
W
AND (∧) operator and addition is replaced with the OR (∨) operator, and yi = Mi,∗ ⊙x = N
x
∧mij =
j
j=1
WN
j=1,xj =1 mij for i = 1, . . . , k.
W
W
W
T
The union of r columns of M is defined as follows: ri=1 Mji = ( ri=1 m1ji , . . . , ri=1 mtji ) . A
column is said to not be included in another column if there exists a row such that the entry in the first
column is 1 and the entry in the second column is 0. If M is a (d + 1)-disjunct matrix satisfying the
property that the union of at most (d + 1) columns does not include any remaining column, x can always
be recovered from y. We need M to be a (d + 1)-disjunct matrix that can be efficiently decoded, as
in [11], [10], to identify at most d defective items in u-NATGT. A k × N strongly explicit matrix is a
matrix in which the entries can be computed in time poly(k). We can now state the following theorem:

Theorem 1. [10, Theorem 16] Let 1 ≤ d ≤ N. There exists a strongly explicit k × N (d + 1)-disjunct
matrix with k = O(d2 log N) such that for any k × 1 input vector, the decoding procedure returns the set
of defective items if the input vector is the union of at most d + 1 columns of the matrix in poly(k) time.
C. Completely separating matrix
We now introduce the notion of completely separating matrices which are used to get efficient decoding
algorithms for (d, u, N)-NATGT. A (u, w)-completely separating matrix is defined as follows:
Definition 1. An h × N matrix G = (gij )1≤i≤h,1≤j≤N is called a (u, w)-completely separating matrix if
for any pair of subsets I, J ⊂ [N] such that |I| = u, |J| = w, and I ∩ J = ∅, there exists row l such
that glr = 1 for any r ∈ I and gls = 0 for any s ∈ J. Row l is called a singular row to subsets I and J.
When u = 1, G is called a w-disjunct matrix.
This definition is slightly different from the one described by Lebedev [17]. It is easy to verify that, if
a matrix is a (u, w)-completely separating matrix, it is also a (u, v)-completely separating matrix for any
v ≤ w. Below we present the existence of such matrices.
Theorem 2. Given integers 1 ≤ u, w < N, there exists a (u, w)-completely separating matrix of size
h × N, where


eN
(u + w)2  ew u
e(u + w)
h =
(u + w) log
·
+ u log
+1
u+w
u
u(2u + w) u

and e is base of the natural logarithm.

Proof: An h × N matrix G = (gij )1≤i≤h,1≤j≤N is generated randomly in which each entry gij is
assigned to 1 with probability of p and to 0 with probability of 1 − p. For any pair of subsets I, J ⊂ [N]
such that |I| = u, |J| = w, the probability of a row is not singular is:
1 − pu (1 − p)w

4

(3)

Then, the probability that there is no singular row to subsets I and J is:
f (p) = (1 − pu (1 − p)w )h

(4)

Using union bound, the probability that any pair of subsets I, J ⊂ [N] such that |I| = u, |J| = w does
not have a singular row, i.e., the probability that G is not a (u, w)-separating matrix, is:






u+w
N
u+w
N
(1 − pu (1 − p)w )h
(5)
f (p) =
g(p, h, u, w, N) =
u
u+w
u
u+w
To ensure that there exists G which is a (u, w)-separating matrix, one needs to find p and h such that
u
, we have:
g(p, h, u, w, N) < 1. Choose p = u+w
u+w !h
 u u 
u
u
w h
f (p) = (1 − p (1 − p) ) = 1 −
1−
(6)
w
u+w
u+w !
 u u 
u
1−
, where exp(x) = ex
(7)
≤ exp −h
w
u+w




 u u
 u u w(2u + w) 
u2
−u
≤ exp −h
1−
= exp −h
(8)
·e
w
(u + w)2
ew
(u + w)2



x n
x2
−x
x
We get (7) because 1 − x ≤ e for any x > 0 and (8) because 1 + n ≥ e 1 − n for n > 1,
|x| ≤ n. Then we have:
u+w 
u




e(u + w)
eN
u+w
N
f (p) ≤
f (p) (9)
g(p, h, u, w, N) =
u+w
u
u
u+w
u+w 
u


 u u w(2u + w) 
e(u + w)
eN
(10)
· exp −h
≤
u+w
u
ew
(u + w)2
<1
(11)

u+w 
u

  
eN
e(u + w)
u u w(2u + w)
⇐⇒
(12)
< exp h
u+w
u
ew
(u + w)2


(u + w)2  ew u
eN
e(u + w)
·
⇐⇒
h > (u + w) log
+ u log
(13)
u+w
u
w(2u + w) u

k
We got (9) because nk ≤ en
and (10) by using (8). From (13), if we choose
k


(u + w)2  ew u
e(u + w)
eN
·
+ u log
+1
(14)
h = (u + w) log
u+w
u
w(2u + w) u

then g(p, h, u, w, N) < 1, i.e., there exists a (u, w)-completely separating matrix of size h × N.
Suppose that G is an h × N (u, w)-completely separating matrix. If w is set to d − u, then every
h × d submatrix, which is constructed by its d columns, is a (u, d − u)-completely separating matrix.
This property is strict and makes the number of rows in G is high. To reduce the number of rows, we
relax this property as follows: each h × d submatrix, which is constructed by d columns of G, is a
(u, d − u)-completely separating matrix with high probability. The following corollary describes this idea
in details.

5

Corollary 1. Let u, d, N be any given positive integers such that 1 ≤ u < d < N. For any ǫ > 0, there
exists an h × N matrix such that each h × d submatrix, which is constructed by its d columns, is a
(u, d − u)-completely separating matrix with probability at least 1 − ǫ, where
u 


ed
1
e(d − u)
d2
u log
+ log
h = 2
d − u2
u
u
ǫ
and e is base of the natural logarithm.

Proof: An h × N matrix G = (gij )1≤i≤h,1≤j≤N is generated randomly in which each entry gij is
assigned to 1 with probability of ud and to 0 with probability of 1 − ud . Our task is now to prove that each
h × d matrix G ′ , which is constructed by d columns of G, is a (u, d − u)-completely
separating
matrix with
u


e(d−u)
d2
1
ed
probability at least 1 − ǫ for any ǫ > 0. Specifically, we prove that h = d2 −u2
+
log
u
log
u
u
ǫ
is sufficient to achieve such G ′ . Similar to the proof in Theorem 2, the probability that G ′ is not a
(u, d − u)-completely separating matrix at most ǫ is
h  u


 
 u u 
 u u 
u d−u
u d−u
ed
d
1−
1−
(15)
1−
≤
exp −h
d
d
u
d
d
u
 u
u



(d − u)(d + u)
ed
u
≤
exp −h
(16)
u
e(d − u)
d2
≤ǫ
(17)
 u
u 2

 
d − u2
1 ed
u
(18)
⇐⇒
≤ exp h
ǫ u
e(d − u)
d2
u 


d2
ed
e(d − u)
1
⇐⇒
h≥ 2
u log
(19)
+ log
d − u2
u
u
ǫ



n
x n
en k
−x
.
(16)
is
derived
because
1
+
≥
We get (15)
because
1
−
x
≤
e
for
any
x
>
0
and
≤
k
n
k

x2
x
e 1 − n for n > 1, |x| ≤ n. This completes our proof.

III. P ROPOSED SCHEME
The basic idea of our scheme, which uses a divide and conquer strategy, is to create at least κ rows,
e.g., i1 , i2 , . . . , iκ such that |Si1 | = · · · = |Siκ | = u and Si1 ∪ . . . ∪ Siκ = S. Then we “map” these rows by
using a special matrix that enables us to convert the outcome in NATGT to the outcome in CNAGT. The
defective items in each row can then be efficiently identified. We present a particular matrix that achieves
efficient decoding for each row in the following section.

A. When the number of defective items equals the threshold
In this section, we consider a special case in which the number of defective items equals the threshold,
i.e., |x| = u. Given a measurement matrix M and a representation vector of u defective items x (|x| = u),
def
def
def
def
what we observe is y = M ⊗ x = (y1 , . . . , yk )T . Our objective is to recover y′ = M ⊙ x = (y1′ , . . . , yk′ )T
from y. Then x can be recovered if we choose M as a (d + 1)-disjunct matrix described in Theorem 1.
To achieve this goal, we create a measurement matrix:
 
M
def
(20)
A=
M
where M = (mij ) is a k × N (d + 1)-disjunct matrix as described in Theorem 1 and M = (mij ) is
the complement matrix of M, mij = 1 − mij for i = 1, . . . , k and j = 1, . . . , N. We note that M can
6

be decoded in time poly(k) = poly(d2 log N) because k = O(d2 log N). Let us assume that the outcome
vector is z. Then we have:

  
M ⊗ x def y
def
def
(21)
z=A⊗x=
=
y
M⊗x
where y = M ⊗ x = (y1 , . . . , yk )T and y = M ⊗ x = (y 1 , . . . , y k )T . The following lemma shows that
y′ = M ⊙ x is always obtained from z; i.e., x can always be recovered.
Lemma 1. Given integers 2 ≤ u ≤ d < N, there exists a strongly explicit 2k × N matrix such that if
there are exactly u defective items among N items in u-NATGT, the u defective items can be identified
in time poly(k), where k = O(d2 log N).
Proof: We construct the measurement matrix A in (20) and assume that z is the observed vector as
in (21). Our task is to create vector y′ = M ⊙ x from z. One can get it using the following rules, where
l = 1, 2, . . . , k:
1) If yl = 1, then yl′ = 1.
2) If yl = 0 and y l = 1, then yl′ = 0.
3) If yl = 0 and y l = 0, then yl′ = 1.
We now prove the correctness of the above rules. Because yl = 1, there are at least u defective items in
row Ml,∗ . Then, the first rule is implied.
If yl = 0, there are less than u defective items in row Ml,∗. Because |x| = u, y l = 1, and the threshold
is u, there must be u defective items in row Ml,∗. Moreover, since Ml,∗ is the complement of Ml,∗ , there
must be no defective item in test l of M. Therefore, yl′ = 0, and the second rule is implied.
If yl = 0, there are less than u defective items in row Ml,∗ . Similarly, if y l = 0, there are less than u
defective items in row Ml,∗ . Because Ml,∗ is the complement of Ml,∗ , the number of defective items in
row Ml,∗ or Ml,∗ cannot be equal to zero, since either yl would equal 1 or y l would equal 1. Since the
number of defective items in row Ml,∗ is not equal to zero, the test outcome is positive, i.e., yl′ = 1. The
third rule is thus implied.
Since we get y′ = M ⊙x, M is a (d + 1)-disjunct matrix and u ≤ d, u defective items can be identified
in time poly(k) by Theorem 1.
Example: We demonstrate Lemma 1 by setting u = d = 2, k = 9, and N = 12 and defining a 9 × 12
2-disjunct matrix M with the first two columns as follows:
 
 

 

1
0
0 0 0 0 0 0 1 1 1 1 0 0
0
1
0
 0 0 0 1 1 1 0 0 0 1 0 0 
0
 
 

 

0
1
 1 1 1 0 0 0 0 0 0 1 0 0 
1
 
 

 

1
0
 0 0 1 0 0 1 0 0 1 0 1 0 
0
  ′  

 

0
0
1
0
0
1
0
0
1
0
0
1
0
0
(22)
M=
 , y =   , y =   , y = 1
0
1
 1 0 0 1 0 0 1 0 0 0 1 0 
0
 
 

 

0
1
 0 1 0 1 0 0 0 0 1 0 0 1 
0
 
 

 

1
0
 0 0 1 0 1 0 1 0 0 0 0 1 
0
0
1
1 0 0 0 0 1 0 1 0 0 0 1
0
Assume that the defective items are 1 and 2, i.e., x = [1, 1, 0, 0, 0, 0, 0, 0, 0]T ; then the observed vector
is z = [yTWyT ]T . Using the three rules in the proof of Lemma 1, we obtain vector y′ . We note that
y′ = M1 M2 = M ⊙ x. Using a decoding algorithm (which is omitted in this example), we can
identify items 1 and 2 as defective items from y′ .

7

B. Encoding procedure
To implement the divide and conquer strategy, we need to divide the set of defective items into small
⌉≥1
subsets such that defective items in those subsets can be effectively identified. We define κ = ⌈ |S|
u
as an integer, and create a h × N matrix G containing κ rows, denoted as i1 , i2 , . . . , iκ , with probability
at least 1 − ǫ such that (i) |Si1 | = · · · = |Siκ | = u and (ii) Si1 ∪ . . . ∪ Siκ = S for any ǫ ≥ 0 where Si is
the set of indices of defective items in row Gi,∗ . For example, if N = 6, the defective items are 1, 2, and
3, and G1,∗ = (1, 0, 1, 0, 1, 1), then S1 = {1, 3}. These conditions guarantee that all defective items will
be included in the decoded set.
To achieve such a G, for any |S| ≤ d, a pruning matrix G ′ of size h×d after removing N −d columns Gx
for x ∈ [N]\S must be a (u, d−u)-completely separating matrix with high probability. From Definition 1,
G ′ is also a (u, |S| − u)-completely separating matrix. Then, the κ rows are chosen as follows. We choose
a collection of sets of defective items: Pl = {j(l−1)u+1 , . . . , jlu } for l = 1, . . . , κ − 1. P ′ is a set satisfying
κ−1
′
′
P ′ ⊆ ∪κ−1
l=1 Pl and |P | = κu − |S|. Then we pick the last set as follows: Pκ = S \ ∪l=1 Pl ∪ P . From
Definition 1, for any Pl , there exists a row, denoted il , such that gil x = 1 for x ∈ Pl and gil y = 0
for y ∈ S \ Pl , where l = 1, . . . , κ. Then, Sil = Pl and row il is singular to sets Sil and S \ Sil for
l = 1, . . . , κ. Condition (i) thus holds. Condition (ii) also holds because ∪κl=1 Sil = ∪κl=1 Pl = S. The
matrix G is specified in section IV.
After creating the matrix G, we generate matrix A as in (20). Then the final measurement matrix T of
size (2k + 1)h × N is created as follows:


G1,∗


M × diag(G1,∗ ) 
G1,∗


A × diag(G1,∗ ) M × diag(G1,∗ ) 




..
..



T =
(23)
=
.
.


 




Gh,∗
Gh,∗



A × diag(Gh,∗ )
M × diag(Gh,∗ )
M × diag(Gh,∗ )
The vector observed using u-NATGT after performing the tests given by the measurement matrix T is




G1,∗
G1,∗ ⊗ x
A × diag(G1,∗ ) 
 A ⊗ x1 




.
..
⊗x=

..
y =T ⊗x = 
.







G
G ⊗ x
h,∗

h,∗

A × diag(Gh,∗ )
A ⊗ xh
  

G1,∗ ⊗ x
y1
 
M ⊗ x1   y1 
y1
  

M ⊗ x1  y1  z1 
  .  .

..
 =  ..  =  .. 
= 
.
    

 G ⊗ x   y  y 
h
  h
 h,∗
M ⊗ xh  yh 
zh
yh
M ⊗ xh
def

(24)

def

where xi = diag(Gi,∗ ) × x, yi = Gi,∗ ⊗ x, yi = M ⊗ xi = (yi1 , . . . , yik )T , yi = M ⊗ xi = (y i1 , . . . , yik )T ,
and zi = [yiT yTi ]T for i = 1, 2, . . . , h.
We note that xi is the vector representing the defective items corresponding to row Gi,∗ . If xi =
(xi1 , xi2 , . . . , xiN )T , Si = {l | xil = 1, l ∈ [N]}. We thus have |Si | = |xi | ≤ d. Moreover, yi = 1 if and
only if |xi | ≥ u.
8

C. The decoding procedure
′
′ T
The decoding procedure is summarized as Algorithm 1, where yi′ = (yi1
, . . . , yik
) is presumed to be
M ⊙ xi . The procedure is briefly explained as follows: Line 2 enumerates the h rows of G. Line 3 checks
if there are at least u defective items in row Gi,∗ . Lines 4 to 14 calculate yi′ , and Line 16 checks if all
items in Gi are truly defective and adds them into S.
Algorithm 1 Decoding procedure for u-NATGT
Input: Outcome vector y, M, M, T .
Output: The set of defective items S.
1: S = ∅.
2: for i = 1 to h do
3:
if yi = 1 then
4:
for l = 1 to k do
5:
if yil = 1 then
6:
yil′ = 1
7:
end if
8:
if yil = 0 and y il = 1 then
9:
yil′ = 0
10:
end if
11:
if yil = 0 and y il = 0 then
12:
yil′ = 1
13:
end if
14:
end for
15:
Decode yi′ usingWM to get the defective set Gi .
16:
if |Gi | = u and j∈Gi Mj ≡ yi then
17:
S = S ∪ Gi .
18:
end if
19:
end if
20: end for
21: Return S.
D. Correctness of the decoding procedure
Our objective is to recover xi from yi and zi for i = 1, 2, . . . , h. Line 2 enumerates the h rows of G.
We have that yi is the indicator that whether there are at least u defective items in row Gi,∗ . If yi = 0, it
implies that there are less than u defective items in row Gi,∗ . Since we only focus on row Gi,∗ which has
exactly u defective items, zi is not considered if yi = 0. Lines 3 does this task.
When yi = 1, it implies that there are at least u defective items in row Gi,∗ . If there are exactly u
defective items in this row, they are always identified as described in Lemma 1. Our task now is to
prevent accusing false defective items by decoding yi′ .
Lines 4 to 14 calculates yi′ from zi . We do not know that yi′ is the union of many columns in M, i.e.,
how many defective items are in row Gi,∗ . Therefore, our task is to decode yi′ using matrix M to get the
defective set Gi , then validate whether all items in Gi are defective.
There exists at least κ rows of G such that there are exactly u defective items in each row. And all
defective items in these rows are the defective items we need to identify. Therefore, we only consider the
case when the number of defective items obtained from decoding yi′ equals to u, i.e., |Gi | = u. Our task
is now to prevent identifying false defective items, which is described in Line 16. There are two sets of
9

defective items corresponding to zi : the first one is the true set, which is Si and unknown, and the second
one is Gi , which is expected to be Si (but not sure) and |Gi | = u. If Gi ≡ Si , we can always identify
u defective items and the condition in line 16 always holds because of Lemma 1. We need to consider
the case Gi 6≡ Si , i.e., there are more than u defective items in row Gi,∗ . We classify this case into two
categories:
1) |Gi \ Si |W= 0: in this case, all elements in Gi are defective items. We do not need to consider
whether j∈Gi Mj ≡ yi . If this condition holds, we receive the true defective items. If it does not
hold, we do not take Gi into the defective
W item set.
2) |Gi \ Si | =
6 0: in this case, we prove that j∈Gi Mj ≡ yi does not hold, i.e., none of elements in Gi
is added to the defective item set. Let pick j1 ∈ Gi \ Si and j2 ∈ Gi \ {j1 }. Since |Si | ≤ d and M is
a (d + 1)-disjunct matrix, there exists a row, denoted τ , such that mτ j1 = 1, mτ j2 = 0, and mτ x = 0
for x ∈ Si . In the other hand, because |Gi | = u and |Si | ≤ d, there is less than u defective
items
W
′
in row τ , i.e., yiτ = 0. Because
x∈Gi mτ x =

W u ≤ |Si |, yiτW= 1. That implies yiτ = 0. However,
W
W
W
′
miτ =
1 = 1 6= 0 = yiτ . Therefore, j∈Gi Mj 6≡ yi .
x∈Gi \{j1 } mτ x
x∈Gi \{j1 } mτ x
Thus, line 16 eliminates all false defective items. Line 21 just returns the defective item set S.
E. The decoding complexity
Because T is constructed using G and M, the probability of successful decoding of y depends on these
choices. Given an input vector yi′ , we get the set of defective items from decoding of M. The probability
of successful decoding of y thus depends only on G. Since G has κ rows satisfying (i) and (ii) with
probability at least 1 − ǫ, all |S| defective items can be identified in h × poly(k) time using t = h(2k + 1)
tests with probability of at least 1 − ǫ for any ǫ ≥ 0. We summarize the divide and conquer strategy in
the following theorem:
Theorem 3. Let 2 ≤ u ≤ d < N be integers and S be the defective set. Suppose that an h × N matrix G
contains κ rows, denoted as i1 , . . . , iκ , such that (i) |Si1 | = · · · = |Siκ | = u and (ii) Si1 ∪ . . . ∪ Siκ = S,
where Sil is the index set of defective items in row Gil ,∗ . And suppose that an k × N matrix M is a
(d + 1)-disjunct matrix that can be decoded in time A. Then a (2k + 1)h × N measurement matrix T , as
defined in (23), can be used to identify at most d defective items in u-NATGT in time O(h × A).
The probability of successful decoding depends only on the event that G has κ rows satisfying (i) and
(ii). Specifically, if that event happens with probability at least 1−ǫ, the probability of successful decoding
is also at least 1 − ǫ for any ǫ ≥ 0.
IV. C OMPLEXITY OF PROPOSED SCHEME
We specify the matrix G in Theorem 3 to get the desired number of tests and decoding complexity for
identifying at most d defective items. Specifying G leads to two approaches on decoding: deterministic
and randomized. Deterministic decoding is a deterministic scheme in which all defective items can be
found with probability 1. It is achievable when every its h × d submatrices, which are constructed by
its d columns, are (u, d − u)-completely separating matrices. Randomized decoding reduces the number
of tests; all defective items can be found with probability at least 1 − ǫ for any ǫ > 0. It is achievable
when each its h × d submatrix, which is constructed by its d columns, is (u, d − u)-completely separating
matrix with probability at least 1 − ǫ.
A. Deterministic decoding
The following theorem states that there exists a deterministic algorithm for identifying all defective
items by choosing G of size h × N to be a (u, d − u)-completely separating matrix in Theorem 2.

10

Theorem 4. Let 2 ≤ u ≤ d ≤ N. There exists a t × N matrix such that at most d defective items in
t
× poly(d2 log N), where
u-NATGT can be identified in time O(d2 log
N)
u 




N
e(d − u)
d
d2
2
· d log N
· d log + u log
t=O
d2 − u 2
u
d
u

Proof: On the basis of Theorem 3, a t × N measurement matrix T is generated as follows:
1) Choose anh × N (u, d − u)-completely separating matrix G as in Theorem 2, where
u

2
h = d2d−u2 e(d−u)
+ u log ed
+ 1.
· d log eN
u
d
u
2) Choose a k × N (d + 1)-disjunct matrix M as in Theorem 1, where k = O(d2 log N) and the
decoding time of M is poly(k).
3) T is defined as in (23).
Since G is a h × d (u, d − u)-completely separating matrix, for any |S| ≤ d, an h × d pruning matrix
′
G , which is created by removing N − d columns Gx for x ∈ [N] \ S, is also a (u, d − u)-completely
separating matrix with probability 1. From Definition 1, G ′ is also a (u, |S| − u)-completely separating
matrix. Then, there exists κ rows satisfying (i) and (ii) as described in section III-B. From Theorem 3,
d defective items can be recovered using t = h × O(d2 log N) tests with probability at least 1, i.e., the
probability 1, in time h × poly(k).
B. Randomized decoding
For randomized decoding, G is chosen such that the pruning matrix G ′ of size h×d created by removing
N − d columns Gx of G for x ∈ [N] \ S is a (u, d − u)-completely separating matrix with probability at
least 1 − ǫ for any ǫ > 0. This results is an improved number of tests and decoding time compared to
Theorem 4:
Theorem 5. Let 2 ≤ u ≤ d ≤ N. For any ǫ > 0, at most d defective items in u-NATGT can be identified
using
u 




d
d2
1
e(d − u)
2
t = O
u log + log
· d log N
d2 − u2
u
u
ǫ
tests with probability at least 1 − ǫ. The decoding time is

t
O(d2 log N )

× poly(d2 log N).

Proof: On the basis of Theorem 3, a t × N measurement matrix T is generated
as follows:
u

2
e(d−u)
1
ed
1) Choose an h × N matrix G as in Corollary 1, where h = d2d−u2
+
log
.
u
log
u
u
ǫ
2
2) Generate a k × N (d + 1)-disjunct matrix M using Theorem 1, where k = O(d log N) and the
decoding time of M is poly(k).
3) Define T as (23).
Let G be an h × N matrix as described in Corollary 1. Then for any |S| ≤ d, an h × d pruning matrix
G ′ , which is created by removing N − d columns Gx for x ∈ [N] \ S, is a (u, d − u)-completely separating
matrix with probability at least 1 − ǫ. From Definition 1, G ′ is also a (u, |S| − u)-completely separating
matrix. Then, there exists κ rows satisfying (i) and (ii) as described in section III-B with probability at
least 1 − ǫ. From Theorem 3, |S| defective items can be recovered using t = h × O(d2 log N) tests with
probability at least 1 − ǫ in time h × poly(k).
V. C ONCLUSION
We introduced an efficient scheme for identifying defective items in NATGT. However, the algorithm
works only for g = 0. Extending the results to g > 0 is left for future work. Moreover, it would be
interesting to consider noisy NATGT as well, in which erroneous tests are present in the test outcomes.
11

VI. ACKNOWLEDGEMENT
The first author thanks to SOKENDAI for supporting him via The Short-Stay Abroad Program 2017.
R EFERENCES
[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] P. Damaschke, “Threshold group testing,” in General theory of information transfer and combinatorics, pp. 707–718, Springer, 2006.
[3] M. Farach, S. Kannan, E. Knill, and S. Muthukrishnan, “Group testing problems with sequences in experimental molecular biology,”
in Compression and Complexity of Sequences 1997. Proceedings, pp. 357–367, IEEE, 1997.
[4] J. Wolf, “Born again group testing: Multiaccess communications,” IEEE Transactions on Information Theory, vol. 31, no. 2, pp. 185–
191, 1985.
[5] G. Cormode and S. Muthukrishnan, “What’s hot and what’s not: tracking most frequent items dynamically,” ACM Transactions on
Database Systems (TODS), vol. 30, no. 1, pp. 249–278, 2005.
[6] D. Du and F. Hwang, Combinatorial group testing and its applications, vol. 12. World Scientific, 2000.
[7] H.-B. Chen and A. De Bonis, “An almost optimal algorithm for generalized threshold group testing with inhibitors,” Journal of
Computational Biology, vol. 18, no. 6, pp. 851–864, 2011.
[8] H. Chang, H.-B. Chen, H.-L. Fu, and C.-H. Shi, “Reconstruction of hidden graphs and threshold group testing,” Journal of combinatorial
optimization, vol. 22, no. 2, pp. 270–281, 2011.
[9] E. Porat and A. Rothschild, “Explicit non-adaptive combinatorial group testing schemes,” Automata, languages and programming,
pp. 748–759, 2008.
[10] H. Q. Ngo, E. Porat, and A. Rudra, “Efficiently decodable error-correcting list disjunct matrices and applications,” in International
Colloquium on Automata, Languages, and Programming, pp. 557–568, Springer, 2011.
[11] M. Cheraghchi, “Noise-resilient group testing: Limitations and constructions,” Discrete Applied Mathematics, vol. 161, no. 1, pp. 81–95,
2013.
[12] S. Cai, M. Jahangoshahi, M. Bakshi, and S. Jaggi, “Grotesque: noisy group testing (quick and efficient),” in Communication, Control,
and Computing (Allerton), 2013 51st Annual Allerton Conference on, pp. 1234–1241, IEEE, 2013.
[13] M. Cheraghchi, “Improved constructions for non-adaptive threshold group testing,” Algorithmica, vol. 67, no. 3, pp. 384–417, 2013.
[14] G. De Marco, T. Jurdziński, M. Różański, and G. Stachowiak, “Subquadratic non-adaptive threshold group testing,” in International
Symposium on Fundamentals of Computation Theory, pp. 177–189, Springer, 2017.
[15] H.-B. Chen and H.-L. Fu, “Nonadaptive algorithms for threshold group testing,” Discrete Applied Mathematics, vol. 157, no. 7,
pp. 1581–1585, 2009.
[16] C. L. Chan, S. Cai, M. Bakshi, S. Jaggi, and V. Saligrama, “Stochastic threshold group testing,” in Information Theory Workshop
(ITW), 2013 IEEE, pp. 1–5, IEEE, 2013.
[17] V. S. Lebedev, “Separating codes and a new combinatorial search model,” Problems of Information Transmission, vol. 46, no. 1, pp. 1–6,
2010.

12

