Improved Constructions for Non-adaptive Threshold Group Testing Mahdi Cheraghchi ∗ 1 1 Abstract 0 The basic goal in combinatorial group testing is to identify a set of up to d defective items 2 within a large population of size n d using a pooling strategy. Namely, the items can be g ≫ grouped together in pools, and a single measurement would reveal whether there are one or u A more defectives in the pool. The threshold model is a generalization of this idea where a mea- surement returns positive if the number of defectives in the pool exceeds a fixed threshold 1 u, negative if this number is below a fixed lower threshold ℓ u, and may behave arbitrar- ≤ ily otherwise. We study non-adaptive threshold group testing (in a possibly noisy setting) ] M and show that, for this problem, O(dg+2(logd)log(n/d)) measurements (where g := u ℓ and − u is any fixed constant) suffice to identify the defectives, and also present almost matching D lowerbounds. Thissignificantlyimprovesthepreviouslyknown(non-constructive)upperbound s. O(du+1log(n/d)). Moreover, we obtain a framework for explicit construction of measurement c schemes using lossless condensers. The number of measurements resulting from this scheme [ is ideally bounded by O(dg+3(logd)logn). Using state-of-the-art constructions of lossless con- 2 densers, however,we come up with explicit testing schemes with O(dg+3(logd)quasipoly(logn)) v and O(dg+3+βpoly(logn)) measurements, for arbitrary constant β >0. 4 4 2 1 Introduction 2 . 2 Combinatorial group testing is a classical problem that deals with identification of sparse Boolean 0 0 vectors usingdisjunctivequeries. Supposethat amongalarge set of nitems it issuspectedthat, for 1 some sparsity parameter d n, up to d items might be “defective”. In technical terms, defective : ≪ v items are known as positives and the rest are called negatives. In a pooling strategy, the items may i X be arbitrarily grouped in pools, and a single “measurement” reveals whether there is one or more r positives within the chosen pool. The basic goal in group testing to design the pools in such a way a that the set of positives can be identified from a number of measurements that is substantially less than n. Since its introduction in 1940’s [15], group testing and its variations have been extensively studied and have found surprisingly many applications in seemingly unrelated areas. In particular, we mention applications in molecular biology and DNA library screening (cf. [3,19,27,29,33,38, 39] and the references therein), multi-access communication [37], data compression [23], pattern matching [11], streaming algorithms [12], software testing [2], compressed sensing [13], and secure key distribution [5], among others. We refer the reader to [16,17] for an extensive review of the major results in this area. ∗Department of Computer Science, University of Texas at Austin, USA. Email: [email protected]. Part of workwasdonewhiletheauthorwaswiththeSchoolofComputerandCommunicationSciences,EcolePolytechnique F´ed´erale de Lausanne (EPFL), Switzerland. Research was supported in part by the ERC Advanced investigator grant 228021 of A. Shokrollahi. A preliminary summary of this work appears (under the same title) in proceedings of the37th InternationalColloquium on Automata,Languages andProgramming (ICALP2010), Bordeaux, France, July 2010 [10]. 1 Formally, in classical group testing one aims to learn an unknown d-sparse1 Boolean vector (x ,...,x ) 0,1 n using a set of m measurements, where each measurement is defined by a 1 n ∈ { } subset of the coordinates [n] and outputs the logical “or” x . The goal is then to design I ⊆ i i the measurements in such a way that all d sparse vectors become u∈nIiquely identifiable using as few W number of measurements as possible. Anaturalgeneralization of classical grouptesting (thatwecall threshold testing), introducedby Damaschke [14], considers the case wherethemeasurement outcomes are determinedby a threshold predicate instead of the logical or. Namely, this model is characterized by two integer parameters ℓ,u such that 0 < ℓ u (that are considered fixed constants), and each measurement outputs ≤ positive if the number of positives within the corresponding pool is at least u. On the other hand, if the number of positives is strictly less than2 ℓ, the test returns negative, and otherwise the outcome can be arbitrary. In this view, classical group testing corresponds to the special case where ℓ = u = 1. In addition to being of theoretical interest, the threshold model is interesting for applications, in particular in biology, where the measurements have reduced or unpredictable sensitivity or may depend on various factors that must be simultaneously present in the sample to result in a positive outcome. The difference g := u ℓ between the thresholds is known as the gap parameter. As shown − by Damaschke [14], in threshold group testing identification of the set of positives is only possible when the number of positives is at least u. Moreover, regardless of the number of measurements, in general the set of positives can be only approximately identified within up to g false positives and g false negatives (thus, unique identification can only be guaranteed when ℓ = u). Additionally, Damaschke constructed a scheme for identification of the positives in the threshold model. For the gap-free casewhereg = 0, thenumberof measurements inthis schemeis O(dlogn), which is nearly optimal (within constant factors). However, when g > 0, the number of measurements becomes O(dnb+du), for an arbitrary constant b > 0, if up to g+(u 1)/b misclassifications are allowed. − A drawback of the scheme presented by Damaschke is that the measurements are adaptive; i.e., the group chosen by each measurement can depend on the outcomes of the previous ones. For numerous applications (in particular, in molecular biology), adaptive measurements are infeasible and must be avoided. In a non-adaptive setting, all measurements must be specified before their outcomes are revealed. This makes it convenient to think of the measurements in a matrix form. Specifically, a non-adaptive measurement matrix is an m n Boolean matrix whose ith row is the × characteristic vector of the set of items participating in the ith pool, and the goal would be to design a suitable measurement matrix. More recently, non-adaptive threshold testing has been considered by Chen and Fu [6]. They observethatageneralizationofthestandardnotionofdisjunctmatrices,thelatterbeingextensively usedintheliteratureofclassical grouptesting, issuitableforthethresholdmodel. Throughoutthis work, we referto thisgeneralized notion as strongly disjunct matrices andtothestandardnotion as classical disjunctmatrices. Usingstronglydisjunctmatrices,theyshowthatO(edu+1log(n/d))non- adaptive measurements suffices to identify the set of positives (within g false positives/negatives) even if up to e erroneous measurements are allowed in the model. This number of measurements almost matches (up to constant factors) the known lower boundson the number of rows of strongly disjunct matrices. However, the dependence on the sparsity parameter is du+1, which might be prohibitive for an interesting range of parameters, when the thresholds are not too small (e.g., ℓ = u= 10) and the sparsity parameter is rather large (e.g., d = n1/10). 1A vector is d-sparse if its support has size at most d. 2 The original paper of Damaschke [14] uses a slightly different convention where the test returns negative if the numberofpositivesinthegroupisat most ℓ. Accordinglyhedefinesthegap betweenthethresholdstobeu−ℓ−1, as opposed to u−ℓ in our paper. 2 In this work, we consider the non-adaptive threshold model in a possibly noisy setting, where a number of measurement outcomes (specified by an error parameter e 0) may be incorrect. ≥ Our first observation is that, a new variation of classical disjunct matrices (that is in general strictly weaker than strongly disjunct matrices) suffices for the purpose of threshold group test- ing. Moreover, we show that this weaker notion is necessary as well, and thus, precisely captures the combinatorial structure of the non-adaptive threshold model. Using a randomness-efficient probabilistic construction (that requires poly(d,logn) bits of randomness), we construct general- ized disjunct matrices with O(dg+2(logd)log(n/d)) rows. Thus, we bring the exponent of d in the asymptotic number of measurements from u+ 1 (that is optimal for strongly disjunct matrices) down to g+2, which is independent of the actual choice of the thresholds and only depends on the gap between them. We also show that this tradeoff is essentially optimal. We proceed to define a new auxiliary object, namely the notion of regular matrices, that turns out to be the key combinatorial object in our explicit constructions. Intuitively, given a gap g 0, ≥ a suitable regular matrix M can be used to take any measurement matrix M designed for the 1 2 threshold model with lower threshold ℓ = 1 and higher threshold u = g + 1 and “life” it up to matrix that works for any arbitrary lower threshold ℓ > 1 and the same gap g. Therefore, for ′ instance, in order to address the gap-free model, it would suffice to have a non-adaptive scheme for the classical group testing model with ℓ = u = 1. This transformation is accomplished using a simple product that increases the height of the original matrix M by a multiplicative factor 2 equal to the height of the regular matrix M , while preserving the “low-threshold” distinguishing 1 properties of the original matrix M . 2 Next, we introduce a framework for construction of regular matrices using strong lossless con- densers that are fundamental objects in derandomization theory, and more generally, theoretical computer science. We show that, by using an optimal condenser, it is possible to construct regular matrices with only O(d(logd)logn) rows. This almost matches the upper bound achieved by a probabilistic construction that we also present in this work. To this date, no explicit construction of such optimal lossless condensers is known (though probabilistic constructions are easy to come up with). However, using state of the art in explicit condensers [4,22], we will come up with two explicit constructions of regular matrices with incomparable parameters. Namely, one with O(d(logd)quasipoly(logn)) rows and another with O(d1+βpoly(logn)), whereβ > 0 is any arbitrary constantandtheexponentofthetermpoly(logn)dependsonthechoice ofβ. Bycombiningregular matrices with strongly disjunct ones (designed for the lowered thresholds ℓ = 1 and u = g +1), ′ ′ we obtain our threshold testing schemes. The bounds obtained by our final schemes are summa- rized in Table 1. When the lower threshold ℓ is not too small, our explicit constructions (rows M8 and M9 of Table 1) significantly improve what was previously known to be achievable even using non-constructive proofs. The rest of the paper is organized as follows. In Section 1.1 we introduce preliminary notions and fix some notation. Section 2 reviews the notion of strongly disjunct matrices and introduces our weaker notion (for thegap-free case g = 0), in addition to thenotion of regular matrices and its properties. In Section 3 we develop our construction of regular matrices from lossless condensers, and instantiate the parameters in Section 3.1. This in particular leads to our explicit threshold testing schemes. Finally in Section 4 we consider the case with nonzero gap, and in Section 5 we discuss the future directions. 1.1 Preliminaries For a matrix M, we denote by M[i,j] the entry of M at the ith row and the jth column. Similarly, we denote the ith entry of a vector v by v(i). Thesupport a vector x 0,1 n, denoted by supp(x), ∈ { } 3 Table 1: Summary of the parameters achieved by various threshold testing schemes. The noise parameter p [0,1) is arbitrary, and thresholds ℓ,u = ℓ + g are fixed constants. “Exp” and ∈ “Rnd”respectively indicate explicit andrandomized constructions. “KS” refersto theconstruction of strongly disjunct matrices based on Kautz-Singleton superimposed codes [24], as described in Appendix A (the bounds in rows M1-M5 are obtained by strongly disjunct matrices). Number of rows Tolerable errors Remarks M1 O(du+1log(n/d)) Ω(pdlog(n/d)) Rnd: Random strongly disjunct matrices. (1 p)2 (1 p)2 M2 O(( d )u+−1logn) Ω(pdlog−n) Exp: KS using codes on the GV bound. 1 p 1 p M3 O((d−logn)u+1) Ω(pdlo−gn) Exp: KS using Reed-Solomon codes. 1 p 1 p M4 O(( d−)2u+1logn) Ω(pdlo−gn) Exp: KS using Algebraic Geometric 1 p 1 p − − codes. M5 O((d√logn)u+3/2) Ω(p(d√logn)3/2) Exp: KS using Hermitian codes (d 1 p 1 p ≫ − − √logn). M6 O(dg+2(logd)log(n/d)) Ω(pdlog(n/d)) Rnd: Construction 2. (1 p)2 (1 p)2 M7 O(dg+3(logd)−log2n) Ω(pd2 lo−g2n ) Constructions 4 and 1 combined, assum- (1 p)2 (1 p)2 − − ing optimal condensers and strongly dis- junct matrices. M8 O(dg+3(logd)T2logn) Ω(pd2T2logn) Exp: Constructions 4 and 1 combined (1 p)g+2 1 p − − using Theorem 10 and M2, where T = 2 exp(O(log3logn))= quasipoly(logn). M9 O(dg+3+β T3ℓlogn ) Ω(pd2 βlogn) Exp: Constructions 4 and 1 combined (1 p)g+2 − 1 p − − using Theorem 11 and M2, where β > 0 is any arbitrary constant and T = 3 ((logn)(logd))1+u/β = poly(logn,logd). Ω(dg+2log n+edg+1) e Lower bound (see Section 4). d 4 is a subset of [n] := 1,...,n such that i supp(x) if and only if x(i) = 1. The Hamming weight { } ∈ of x, denote by wgt(x) is defined as supp(x). For an m n Boolean matrix M and S [n], we | | × ⊆ denote by M the m S submatrix of M formed by restricting M to the columns picked by S | × | | S. Moreover, for a vector x 0,1 n, we use M[x] to denote the set of vectors in 0,1 m that ℓ,u ∈ { } { } correctly encode the measurement outcomes resulting from non-adaptive threshold tests defined by the measurement matrix M on x using threshold parameters ℓ,u. In the gap-free case, this set may only have a single element that we denote by M[x] . Thus, for any y M[x] we have y(i) = 1 u ℓ,u ∈ if supp(M ) supp(x) u, and y(i) = 0 if supp(M ) supp(x) < ℓ, where M indicates the jth j j j | ∩ | ≥ | ∩ | row of M. The min-entropy of a distribution with finite support Ω is given by X H ( ) := min log (x) , ∞ X x Ω{− X } ∈ where (x) is the probability that assigns to the outcome x and logarithm is taken to base X X 2. A flat distribution is one that is uniform on its support. For such a distribution , we have X H ( ) = log(supp( )). The statistical distance between two distributions and defined on th∞e sXame finite|spaceXΩ|is given by 1 (s) (s), which is half the ℓ XdistancYe of the two 2 s Ω|X −Y | 1 distributions when regarded as vectors of∈probabilities over Ω. Two distributions and are said P X Y to be ǫ-close if their statistical distance is at most ǫ. We will use the shorthand for the uniform n U distribution on 0,1 n, and X for a random variable X drawn from a distribution . { } ∼ X X The main technical tool that we use in our explicit constructions is the notion of lossless condensers, defined below. Definition 1. A function f: 0,1 n˜ 0,1 t 0,1 ℓ˜ is a strong lossless condenser for entropy { } ×{ } → { } k and with error ǫ (in short, (k,ǫ)-condenser) if for every distribution on 0,1 n˜ with min- X { } entropy at least k, random variable X and a seed Y , the distribution of (Y,f(X,Y)) is t ∼ X ∼ U ǫ-close to some distribution ( , ) with min-entropy at least t+k. A condenser is explicit if it is t U Z polynomial-time computable. We will use the following “almost-injectivity” property of lossless condensers in our proofs. Proposition 2. Let be a flat distribution with min-entropy logK over a finite sample space Ω X and f: Ω Γ be a mapping to a finite set Γ. If f( ) is ǫ-close to having min-entropy logK, then → X there is a set T Γ of size at least (1 2ǫ)K such that ⊆ − ( y T) f(x)= y f(x)= y x = x. ′ ′ ∀ ∈ ∧ ⇒ Proof. Suppose that is uniformly supported on a set S Ω of size K. For each y Γ, define X ⊆ ∈ n := x Ω: f(x) = y . Denote by µ the distribution f( ) over Γ and by µ a distribution on y ′ |{ ∈ }| X Γ with min-entropy K that is ǫ-close to µ, which is guaranteed to exist by the assumption. Define T := y Γ: n = 1 , and similarly, T := y Γ: n 2 . Observe that for each y Γ we have y ′ y { ∈ } { ∈ ≥ } ∈ µ(y) = n /K, and also supp(µ) = T T . Thus, i ′ ∪ T + n = K. (1) y | | y T′ X∈ The fact that µ and µ are ǫ-close implies that ′ µ(y) µ(y) ǫ (n 1) ǫK. ′ y | − | ≤ ⇒ − ≤ y T′ y T′ X∈ X∈ 5 In particular, this means that T ǫK (since by the choice of T , for each y T we have n 2). ′ ′ ′ y | |≤ ∈ ≥ Furthermore, (n 1) ǫK n ǫK + T 2ǫK. y y ′ − ≤ ⇒ ≤ | |≤ y T′ y T′ X∈ X∈ This combined with (1) gives T = K n (1 2ǫ)K y | | − ≥ − y T′ X∈ as desired. 2 Variations of disjunct matrices The combinatorial structure used by Chen and Fu in their non-adaptive scheme is the following generalization of the standard notion of disjunct matrices that we refer to as strongly disjunct matrices throughout this work. Definition 3. A matrix (with at least d+u columns) is said to be strongly (d,e;u)-disjunct if for every choice of d+u columns C ,...,C ,C ,...,C , all distinct, we have 1 u 1′ d′ u supp(C ) d supp(C ) > e. |∩i=1 i \∪i=1 i′ | Observe that, (d,e;u)-disjunct matrices are, in particular, (d,e;u)-disjunct for any d d, ′ ′ ′ ′ ≤ e e, and u u. Moreover, classical (d,e)-disjunct matrices that are extensively used in group ′ ′ ≤ ≤ testing literature (see [16, Ch. 7]) correspond to the special case u = 1. To make the main ideas more transparent, until Section 4 we will focus on the gap-free case where ℓ = u. The extension to nonzero gaps is straightforward and will be discussed in Section 4. Moreover, often we will implicitly assume that the Hamming weight of the Boolean vector that is to be identified is at least u (since otherwise, we know that confusions cannot be avoided), and will take the thresholds ℓ,u as fixed constants. The notion of strongly disjunct matrices, in its general form, has been studied in the literature under different names and equivalent formulations, e.g., superimposed (u,d)-designs/codes and (u,d)cover-freefamilies(see[5,7,18,25,34,35]andthereferencestherein). Animportantmotivation for the study of this notion is the following hidden hypergraph-learning problem (cf. [16, Ch. 12]), itself beingmotivated by the so-called complex model in computational biology [5]: Supposethat G isau-hypergraph3 onavertex setV ofsizen,anddenoteby (G)thesetofvertices inducedbythe V hyper-edge set of G; i.e., v (G) if and only if G has a hyper-edge incident to v. Then assuming ∈ V that (G) d for a sparsity parameter d, the aim is to learn G using as few (non-adaptive) |V | ≤ queries of the following type as possible: Each query specifies a set Q V, and its corresponding ⊆ answer is a Boolean value which is 1 if and only if G has a hyperedge contained in Q. It is known that [5,20], in the hypergraph-learning problem, any suitable grouping strategy defines a strongly disjunct matrix (whose rows are characteristic vectors of individual queries Q), and conversely, any strongly disjunct matrix can be used as the incidence matrix of the set of queries. The parameter e determines “noise tolerance” of the measurement scheme. Namely, a strongly (d,e;u)-disjunct matrix can uniquely distinguish between d-sparse hypergraphs even in presence of up to e/2 ⌊ ⌋ erroneous query outcomes. The key observation made by Chen and Fu [6] is that threshold group testing corresponds to the special case of the hypergraph learning problem where the hidden graph G is known to be a 3That is, a hypergraph where each edge is a set of u vertices. 6 u-clique4. Inthis case, theunknownBoolean vector in thecorrespondingthresholdtesting problem would be the characteristic vector of (G). It follows that strongly disjunct matrices are suitable V choices for the measurement matrices in threshold group testing. Nonconstructively, a probabilistic argument akin to the standard argument for the case of classical disjunct matrices (see [16, Ch. 7]) can be used to show that strongly (d,e;u)-disjunct matricesexistwithm = O(du+1(log(n/d))/(1 p)2)rowsanderrortolerancee = Ω(pdlog(n/d)/(1 − − p)2), for any noise parameter p [0,1). On the negative side, however, several concrete lower ∈ bounds are known for the number of rows of such matrices [18,34,35]. In asymptotic terms, these results show that one must have m = Ω(du+1log n+edu), and thus, the probabilistic upperbound d is essentially optimal. For the underlying strongly disjunct matrix, Chen and Fu [6] use a greedy construction [7] that achieves, for any e 0, O((e+1)du+1log(n/d)) rows, but may take exponential time in the size ≥ of the resulting matrix. Nevertheless, as observed by several researchers [5,18,20,25], a classical explicit construction of combinatorial designs due to Kautz and Singleton [24] can be extended to construct strongly disjunct matrices. This concatenation-based construction transforms any error- correcting code having large distance into a disjunct matrix. While the original construction uses Reed-Solomon codes and achieves nice bounds, it is possible to use other families of codes. In particular, as recently shown by Porat and Rothschild [30], codes on the Gilbert-Varshamov bound (cf. [28]) result in nearly optimal disjunct matrices. Moreover, for a suitable range of parameters, they give a deterministic construction of such codes that runs in polynomial time in the size of the resulting disjunct matrix (albeit exponential in the dimension of the code5). We will elaborate on details of this class of constructions in Appendix A, and will additionally consider a family of algebraic-geometric codes and Hermitian codes which give incomparable bounds,as summarized in Table 1 (rows M2–M5). Even though, as discussed above, the general notion of strongly (d,e;u)-disjunct matrices is sufficient for threshold group testing with upper threshold u, in this section we show that a new, weaker, notion of disjunct matrices defined below (which, as we show later, turns out to be strictly weaker when u > 1), would also suffice. We also define an auxiliary notion of regular matrices. Definition 4. A Boolean matrix M with n columns is called (d,e;u)-regular if for every subset of columns S [n] (called the critical set) and every Z [n] (called the zero set) such that ⊆ ⊆ u S d, Z S , S Z = , there are more than e rows of M at which M has weight S ≤ | | ≤ | | ≤ | | ∩ ∅ | exactly u and (at the same rows) M has weight zero. Any such row is said to u-satisfy S and Z | Z. If, in addition, for every distinguished column i S, more than e rows of M both u-satisfy S ∈ and Z and have a 1 at the ith column, the matrix is called (d,e;u)-disjunct (and the corresponding “good” rows are said to u-satisfy i, S, and Z). To distinguish between the above variant of disjunct matrices and strongly disjunct matrices or classical disjunct matrices, we will refer to our variant as threshold disjunct matrices, or (when there is no risk of confusion) simply disjunct matrices. It is easy to verify that (assuming 2d n) the classical notion of (2d 1,e)-disjunct matri- ≤ − ces is equivalent to strongly (2d 1,e;1)-disjunct and (d,e;1)-disjunct. Moreover, any (d,e;u)- − disjunct matrix is (d,e;u)-regular, (d 1,e;u 1)-regular, and classical (d,e)-disjunct (but the − − reverse implications do not in general hold). Therefore, the above-mentioned lower bound of 4A u-clique on the vertex set V is a u-hypergraph (V,E) such that, for some V′ ⊆V, E is the set of all subsets of V′ of size u. 5In this regard, this construction of disjunct matrices can be considered weakly explicit in that, contrary to fully explicit constructions, it is not clear if each individual entryof thematrix can becomputed in time poly(d,logn). 7 m = Ω(d2log n + ed) that applies for (d,e)-disjunct matrices holds for (d,e;u)-disjunct matri- d ces as well. Below we show that our notion of disjunct matrices is necessary and sufficient for the purpose of threshold group testing: Lemma 5. Let M be an m n Boolean matrix that is (d,e;u)-disjunct. Then for every distinct × d-sparse vectors x,x 0,1 n such that6 supp(x) * supp(x), wgt(x) supp(x) supp(x) and ′ ′ ′ ∈ { } ≥ | \ | wgt(x) u, we have ≥ supp(M[x] ) supp(M[x] ) > e. (2) u ′ u | \ | Conversely, if M satisfies (2) for every choice of x and x as above, it must be ( d/2 ,e;u)-disjunct. ′ ⌊ ⌋ Proof. First, suppose that M is (d,e;u)-disjunct, and let y := M[x] and y := M[x] . Take any u ′ ′ u i supp(x) supp(x), and let S := supp(x) and Z := supp(x) supp(x). Note that S d and by ′ ′ ∈ \ \ | | ≤ assumption, we have Z S . Now, Definition 4 implies that there is a set E of more than e rows | | ≤ | | of M that u-satisfy i as the distinguished column, S as the critical set and Z as the zero set. Thus for every j E, the jth row of M restricted to the columns chosen by supp(x) must have weight ∈ exactly u, while its weight on supp(x) is less than u. Therefore, y(j) = 1 and y (j) = 0 for more ′ ′ than e choices of j. For the converse, consider any choice of a distinguished column i [n], a critical set S [n] ∈ ⊆ containing i (such that S u), and a zero set Z [n] where Z S . Define d-sparse Boolean | | ≥ ⊆ | | ≤ | | vectors x,x 0,1 n so that supp(x) := S and supp(x) := Z (S i ). Let y := M[x] and ′ ′ u ∈ { } ∪ \{ } y := M[x] and E := supp(y) supp(y ). By assumption we know that E > e. Take any j E. ′ ′ u ′ \ | | ∈ Since y(j) = 1 and y (j) = 0, we get that the jth row of M restricted to the columns picked by ′ Z (S i ) must have weight at most u 1, whereas it must have weight at least u whenrestricted ∪ \{ } − to S. As the sets i ,S i , andZ aredisjoint, this can hold only if M[j,i] = 1, and moreover, the { } \{ } jth row of M restricted to the columns picked by S (resp., Z) has weight exactly u (resp., zero). Hence, this row (as well as all the rows of M picked by E) must u-satisfy i,S, and Z, confirming that M is ( d/2 ,e;u)-disjunct. ⌊ ⌋ We will use regular matrices as intermediate building blocks in our constructions of disjunct matrices to follow. The connection with disjunct matrices is made apparent through a direct product of matrices defined in Construction 1. Intuitively, using this product, regular matrices can beused to transform any measurement matrix suitable for the standard group testing modelto one with comparable properties in the threshold model. The following lemma formalizes the idea. Lemma 6. Let M and M be Boolean matrices with n columns, such that M is (d 1,e ;u 1)- 1 2 1 1 − − regular. Let M := M M , and suppose that for d-sparse Boolean vectors x,x 0,1 n such that 1 2 ′ ⊙ ∈ { } 6 Observethat at least one of thetwo possible orderings of any two distinct d-sparse vectors, at least one having weight u or more, satisfies this condition. Given: Boolean matrices M and M that are m n and m n, respectively. 1 2 1 2 • × × Output: An m n Boolean matrix M M , where m := m m . 1 2 1 2 • × ⊙ Construction: Let the rows of M := M M be indexed by the set [m ] [m ]. Then the 1 2 1 2 • ⊙ × row corresponding to (i,j) is defined as the bit-wise or of the ith row of M and the jth row 1 of M . 2 Construction 1: Direct product of measurement matrices. 8 wgt(x) wgt(x), we have ′ ≥ supp(M [x] ) supp(M [x] ) e . 2 1 2 ′ 1 2 | \ | ≥ Then, supp(M[x] ) supp(M[x] ) (e +1)e . u ′ u 1 2 | \ | ≥ Proof. Firstweconsiderthecasewhereu > 1. Lety := M [x] 0,1 m2,y := M [x] 0,1 m2, 2 1 ′ 2 ′ 1 ∈ { } ∈{ } where m is the number of rows of M , and let E := supp(y) supp(y ). By assumption, E e . 2 2 ′ 2 \ | | ≥ Fix any i E so that y(i) = 1 and y (i) = 0. Therefore, the ith row of M must have all zeros ′ 2 ∈ at positions corresponding to supp(x) and there is a j supp(x) supp(x) such that M [i,j] = 1. ′ ′ 2 ∈ \ Define S := supp(x) j , Z := supp(x) supp(x), z := M[x] and z := M[x] . ′ u ′ ′ u \{ } \ As wgt(x) wgt(x), we know that Z S +1. The extreme case Z = S +1 only happens ′ ≥ | |≤ | | | | | | when x and x have disjoint supports, in which case one can remove an arbitrary element of Z to ′ ensure that Z S and the following argument (considering the assumption u > 1) still goes | | ≤ | | through. By the definition of regularity, there is a set E consisting of at least e +1 rows of M that 1 1 1 (u 1)-satisfy the critical set S and the zero set Z. Pick any k E , and observe that z must 1 − ∈ have a 1 at position (k,i). This is because the row of M indexed by (k,i) has a 1 at the jth position (since the kth row of M does), and at least u 1 more 1’s at positions corresponding to 2 − supp(x) j (due to regularity of M ). On the other hand, note that the kth row of M has at 1 1 \{ } most u 1 ones at positions corresponding to supp(x) (because supp(x) S Z), and the ith row ′ ′ − ⊆ ∪ of M has all zeros at those positions (because y (i) = 0). This means that the row of M indexed 2 ′ by (k,i) (which is the bit-wise or of the kth row of M and the ith row of M ) must have less than 1 2 u ones at positions corresponding to supp(x), and thus, z must be 0 at position (k,i). Therefore, ′ ′ z and z differ at position (k,i). ′ Since there are at least e choices for i, and for each choice of i, at least e +1 choices for k, we 2 1 conclude that in at least (e +1)e positions, z has a one while z has a zero. 1 2 ′ The argument for u = 1 is similar, in which case it suffices to take S := supp(x) and Z := supp(x) supp(x). ′ \ As a corollary it follows that, when M is a (d 1,e ;u 1)-regular and M is a (d,e )-disjunct 1 1 2 2 − − matrix, the product M := M M will distinguish between any two distinct d-sparse vectors 1 2 ⊙ (of weight at least u) in at least (e + 1)(e + 1) positions of the measurement outcomes. This 1 2 combined with Lemma 5 would imply that M is, in particular, ( d/2 ,(e + 1)(e + 1) 1;u)- 1 2 ⌊ ⌋ − disjunct. However, using a direct argument similar to the above lemma it is possible to obtain a slightly better result, given by Lemma 7. Lemma 7. Suppose that M is a (d,e ;u 1)-regular and M is a (2d,e )-disjunct matrix. Then 1 1 2 2 − M M is a (d,(e +1)(e +1) 1;u)-disjunct matrix. 1 2 1 2 ⊙ − As a particular example of where Lemma 6 can be used, we remark that the measurement matrices constructed in [9] that are not necessarily disjunct but allow approximation of sparse vectors in highly noisy settings of the standard group testing model (as well as those used in adaptive two-stage schemes; cf. [8] and the references therein), can be combined with regular matrices to offer the same qualities in the threshold model. In the same way, numerous existing results in group testing can be ported to the threshold model by using Lemma 6. 3 Constructions In this section, we obtain several construction of regular and disjunct matrices. Our first construc- tion, described in Construction 2, is a randomness-efficient probabilistic construction that can be 9 analyzed using standard techniques from the probabilistic method. The bounds obtained by this construction are given in Lemma 8 below. The amount of random bits required by this construc- tion is polynomially bounded in d and logn, which is significantly smaller than it would be had we picked the entries of M fully independently. Lemma8. Foreveryp [0,1)andintegerparameter u > 0, Construction2withm = O (dlog(n/d)/(1 ′ u ∈ − p)2)(resp., m = O (d2log(n/d)/(1 p)2))outputsa(d,Ω (pm);u)-regular(resp., (d,Ω (pm/d);u)- ′ u u ′ u ′ − disjunct) matrix with probability 1 o(1). − Proof. We show the claim for regular matrices, the proof for disjunct matrices is similar. Consider any particular choice of a critical set S [n] and a zero set Z [n] such that u S d and ⊆ ⊆ ≤ | | ≤ Z S . Choose an integer i so that 2i 1u S 2iu, and take any j [m]. Denote the (i,j)th − ′ | |≤ | | ≤ | |≤ ∈ row of M by the random variable w 0,1 n, and by q the “success” probability that w has S ∈ { } | weight exactly u and w is all zeros. For an integer ℓ > 0, we will use the shorthand 1ℓ (resp., 0ℓ) Z | for the all-ones (resp., all-zeros) vector of length ℓ. We have q = Pr[(w )= 1u (w )= 0S+Z u] R Z (S R) | | | |− | ∧ | ∪ \ R [S] X⊆ R=u | | = Pr[(w )= 1u] Pr[(w ) = 0S+Z u (w )= 1u] R Z (S R) | | | |− R | · | ∪ \ | | R X (=a) (1/(2i+2u))u (1 Pr[(w )= 0S+Z u (w ) = 1u]) Z (S R) | | | |− R · − | ∪ \ 6 | | R X (b) (1/(2i+2u))u (1 (S + Z u)/(2i+2u)) ≥ · − | | | |− R X u 1 S 1 S 1 | | (1/(2i+2u))u | | (1/(2i+2u))u =:c, (3) ≥ 2 u ≥ 2 u · ≥ 23u+1 uu (cid:18) (cid:19) (cid:18) (cid:19) · where (a) and (b) use the fact that the entries of w are (u+1)-wise independent, and (b) uses an additional union bound. Here the lower bound c > 0 is a constant that only depends on u. Now, let e := mpq. using Chernoff bounds, and independence of the rows, the probability that there ′ are at most e rows (among (i,1),...,(i,m )) whose restrictions to S and Z have weights u and 0, ′ respectively, becomes upper bounded by exp( (mq e)2/(2mq)) = exp( (1 p)2mq/2) exp( (1 p)2mc/2). ′ ′ ′ ′ − − − − ≤ − − Now take a union bound on all the choices of S and Z to conclude that the probability that the Given: Integer parameters n,m,d,u. ′ • Output: An m n Boolean matrix M, where m := m log(d/u) . ′ • × ⌈ ⌉ Construction: Let r := log(d/u) . Index the rows of M by [r] [m]. Sample the (i,j)th ′ • ⌈ ⌉ × row of M independently from a (u+1)-wise independent distribution on n bit vectors, where each individual bit has probability 1/(2i+2u) of being 1. Construction 2: Probabilistic construction of regular and disjunct matrices. 10