key: cord-0621417-n40j6bnh
authors: Price, Eric; Scarlett, Jonathan
title: A Fast Binary Splitting Approach to Non-Adaptive Group Testing
date: 2020-06-18
journal: nan
DOI: nan
sha: 181b40a8fb5cd655d3bcc94fc488e8c195d73dd2
doc_id: 621417
cord_uid: n40j6bnh

In this paper, we consider the problem of noiseless non-adaptive group testing under the for-each recovery guarantee, also known as probabilistic group testing. In the case of $n$ items and $k$ defectives, we provide an algorithm attaining high-probability recovery with $O(k log n)$ scaling in both the number of tests and runtime, improving on the best known $O(k^2 log k cdot log n)$ runtime previously available for any algorithm that only uses $O(k log n)$ tests. Our algorithm bears resemblance to Hwang's adaptive generalized binary splitting algorithm (Hwang, 1972); we recursively work with groups of items of geometrically vanishing sizes, while maintaining a list of"possibly defective"groups and circumventing the need for adaptivity. While the most basic form of our algorithm requires $Omega(n)$ storage, we also provide a low-storage variant based on hashing, with similar recovery guarantees.

Group testing is a classical statistical problem with a combinatorial flavor [4, 19, 20] , and has recently regained significant attention following new applications [14, 17, 25] , connections with compressive sensing [26, 27] , and most recently, utility in testing for COVID-19 [28, 42, 45] . The goal is to identify a defective (or infected) subset of items (or individuals) based on a number of suitably-designed tests, with the binary test outcomes indicating whether or not the test includes at least one defective item.

In both classical studies and recent works, considerable effort has been put into the development of group testing algorithms achieving a given recovery criterion with a near-optimal number of tests [2, 3, 5, 11, 15, 16, 20, 33, 35, 36, 39] , and many solutions are known with decoding time linear or slower in the E. Price is with the Department of Computer Science, University of Texas at Austin (e-mail: ecprice@cs.utexas.edu). J. Scarlett is with the Department of Computer Science and the Department of Mathematics, National University of Singapore (e-mail: scarlett@comp.nus.edu.sg).

E. Price was supported in part by NSF Award CCF-1751040 (CAREER). J. Scarlett was supported by an NUS Early Career Research Award. number of items. In contrast, works seeking to further reduce the decoding time have only arisen more recently [9, 10, 12, 30, 31, 34, 37] ; see Section 1.2 for an overview.

In this paper, we present a non-adaptive group testing algorithm that guarantees high-probability recovery of the defective set with O(k log n) scaling in both the number of tests and the decoding time in the case of n items and k defectives. By comparison, the best previous decoding time alongside O(k log n) tests was O(k 2 log k · log n) [9] , with faster algorithms incurring suboptimal O(k log k · log n) scaling in the number of tests [10, 34] . By a standard information-theoretic lower bound [4, Sec. 1.4] , the O(k log n) scaling in the number of tests is optimal whenever k ≤ n 1−Ω (1) .

Before outlining the related work and contributions in more detail, we formally introduce the problem.

We consider a set of n items indexed by {1, . . . , n}, and let S ⊂ {1, . . . , n} be the set of defective items. The number of defectives is denoted by k = |S|; this is typically much smaller than n, so we assume that k ≤ n 2 . For clarity of exposition, we will present our algorithm and analysis for the case that k is known, but these will trivially extend to the case that only an upper bound k ≥ k is known, and k replaces k in the number of tests and decoding time.

A sequence of t tests X (1) , . . . , X (t) is performed, with X (i) ∈ {0, 1} n indicating which items are in the i-th test, and the resulting outcomes are Y (i) = j∈S X (i) j (i.e., 1 if there is any defective item in the test, 0 otherwise). We focus on the non-adaptive setting, in which all tests X (1) , . . . , X (t) must be designed prior to observing any outcomes.

We consider a for-each style recovery guarantee, in which the goal is to develop a randomized algorithm that, for any fixed defective set S of cardinality k, produces an estimate S satisfying P[ S = S] ≤ δ for some small δ > 0 (typically δ → 0 as n → ∞). In our algorithm, only the tests {X (i) } t i=1 will be randomized, and the decoding algorithm producing S from the test outcomes will be deterministic.

The existing works on group testing vary according to the following defining features [4, 20] :

• For-each vs. for-all guarantees. In combinatorial (for-all) group testing, one seeks to construct a test design that guarantees the recovery of all defective sets up to a certain size. In contrast, in probabilistic (for-each) group testing, the test design may be randomized, and the algorithm is allowed some non-zero probability of error.

Number of tests Decoding time Construction SAFFRON [34] O(k · log k · log n) O(k log k) 1 Randomized GROTESQUE [10] O(k · log k · log n) O(k · log k · log n) Randomized Inan et al. [30] O k·log n·log log n log k O k 3 · log n · log log n log k Explicit BMC [9] O(k log n) O(k 2 · log k · log n) Randomized This Paper O(k log n) O(k log n) Randomized Table 1 : Overview of existing noiseless non-adaptive group testing results with poly(k log n) decoding time under the for-each guarantee, with n items and k defectives.

• Adaptive vs. non-adaptive. In the adaptive setting, each test may be designed based on all previous outcomes, whereas in the non-adaptive setting, all tests must be chosen prior to observing any outcomes.

The non-adaptive setting is often preferable in practice, as it permits the tests to be performed in parallel.

• Noiseless vs. noisy. In the noiseless setting, the test outcomes are perfectly reliable, whereas in noisy settings, some tests may be flipped according to some probabilistic or adversarial noise model.

As outlined in the previous subsection, our focus is on the for-each guarantee, non-adaptive testing, and noiseless tests, but for comparison, we also discuss other variants in this section.

By a simple counting argument, even in the least stringent scenario of noiseless adaptive testing and the for-each guarantee, Ω k log n k tests are required for reliable recovery [6, 36] . In the noiseless adaptive setting, the classical generalized binary splitting algorithm of Hwang [29] matches this bound with sharp constant factors, and attains the stronger for-all guarantee. More recently, O(k log n) adaptive tests and decoding time were shown to suffice under the for-each guarantee in the presence of random noise [10] .

In the non-adaptive setting with the for-each guarantee, a recent of result of [1] shows that n tests are required to attain asymptotically vanishing error probability as n → ∞ with k = βn , for arbitrarily small β > 0. Thus, O(k log n k ) scaling (with a universal implied constant) is impossible; see also [16] . On the other hand, O(k log n) tests do suffice, and this scaling is equivalent to O(k log n k ) in the regime k ≤ n 1−Ω(1) . Early works achieved this for the scaling regime k = O(1) [5, 35, 36] , and a variety of more recent works considered more general k [3, 5, 15, 16, 33, 35, 36, 39] , particularly under "unstructured" random test designs such as i.i.d. Bernoulli [2, 5, 39] and near-constant tests-per-item [15, 33] . In fact, following the recent work of Coja-Oghlan et al. [16] , the precise constants for non-adaptive group testing have been nailed down in the regime k ≤ n 1−Ω(1) , with the algorithm for the upper bound requiring Ω(n) decoding time.

Since non-adaptive algorithms with poly(k log n) decoding time under the for-each guarantee are particularly relevant to the present paper, we provide a summary of the existing works in Table 1 . We separate our discussion according to whether or not each algorithm attains O(k log n) scaling in the number of tests, as we believe this to be a particularly important desiderata in practice when tests are expensive:

• SAFFRON and GROTESQUE both use O(k log k · log n) tests, which is suboptimal by a log k factor.

In particular, SAFFRON's decoding time is as low as O(k log k) in the word-RAM model. 1 While storage requirements were not a significant point of focus in the existing works, we also note (for later comparison) that SAFFRON only requires O(k log k · log n) bits of storage; see Appendix A for details.

• In the regime k = Θ(n α ) with fixed α ∈ (0, 1), Inan et al. [30] attain O(k 3 log n) decoding time with O(k log n) tests, whereas the number of tests becomes suboptimal in sparser regimes such as k = poly(log n). The best previous decoding time for an algorithm that only uses O(k log n) tests is O(k 2 log k · log n), via bit-mixing coding (BMC) [9] . To our knowledge, all other existing algorithms succeeding with O(k log n) tests incur Ω(n) decoding time [3, 5, 15, 16, 33, 35, 36, 39] .

Our main theoretical contribution is to provide an algorithm that attains O(k log n) scaling in both the number of tests and decoding time, as well as using distinct algorithmic ideas from the existing works (see Section 2.1 for discussion). In particular, among the algorithms using O(k log n) tests, ours reduces the dependence on k in the decoding time from quadratic to linear.

It is worth noting that the works [9, 10, 30, 34] also extend their guarantees to noisy settings, and the approach in [30] has the additional advantage of using an explicit test design, i.e., the test vectors X (1) , . . . , X (t) can be constructed deterministically in time polynomial in n and t. Although noisy and/or de-randomized variants of our algorithm may be possible, this is deferred to future work. 2 In addition, [34] demonstrated that O k log n · log 1 tests suffice for SAFFRON in the case that one is only required to identify a fraction 1 − of the defectives, as opposed to the entire defective set. Thus, O(k log n) scaling is maintained for approximate recovery with constant > 0, but not for the more common requirement of exact recovery.

While we have focused our discussion on the for-each setting, the first poly(k log n)-time non-adaptive group testing algorithms were for the more stringent for-all setting [12, 31, 37] . The strength of the for-all guarantee comes at the expense of requiring significantly more tests, e.g., see [23] for an Ω min k 2 log n log k , n lower bound. An O(k 2 log n) upper bound on the number of tests was originally attained with Ω(n) decoding time, [22, 38] , and more recently with poly(k log n) decoding time [31, 37] . The earlier work of [12] attained poly(k log n) decoding time under a list decoding recovery criterion, and also allowed for adversarial noise in the test outcomes.

Before summarizing our main results, we briefly highlight that our algorithmic techniques are distinct from the existing works summarized above (see Section 2.1 for further details), and are more closely related to the adaptive binary splitting approach of Hwang [29] . We first test large groups of items together, placing each group into a single randomly-chosen test among a sequence of O(k) tests. We then "split" these groups into smaller sub-groups, while using the O(k) test outcomes to eliminate those known to be non-defective.

This process is repeated (with the elimination step ensuring that the number of groups under consideration does not grow too large) until a superset of S is found. This superset is shown to be of size O(k) with high probability, and S is deduced from this superset via a final sequence of O(k log k) tests (similar ideas to this final step have appeared in works such as [12, 37] ). Despite the sequential nature of this procedure, the tests can be performed non-adaptively.

Our first main result is informally stated as follows; see Theorem 1 for a formal statement. 

In this section, we introduce our algorithm, and state and prove our main result giving guarantees on its correctness, number of tests, decoding time, and storage. For simplicity of notation, we assume throughout the analysis that k and n are powers of two. Our algorithm only requires an upper bound on the number of defectives, and hence, any other value of k can simply be rounded up to a power of two. In addition, the total number of items n can be increased to a power of two by adding "dummy" non-defective items. 

We propose an algorithm that works with a tree structure, as illustrated in Figure 1 . On the left of the figure,

we have 1 + log 2 n levels, with the top level containing all items, the second level containing two groups with half the items each, and so on, with each level "splitting" the previous levels' groups in half until the final level containing individual items. The ordering of items is inconsequential for our analysis and results provided that the two children of a given node can be identified in constant time, so for convenience we assume the natural order. 3 For = 0, . . . , log 2 n, the j-th group at the -th level is denoted by G Figure 1 (Right), in which each node corresponds to a group of items (e.g., the root corresponds to the set of all items, and the leaves correspond to individual items). The levels of the tree are indexed by = 0, . . . , log 2 n. Our algorithm works down the tree one level at a time, keeping a list of possibly defective (PD) nodes, and performing tests to obtain such a list at the next level, while ideally keeping the size of the list small (e.g., O(k)). When we perform tests at a given level, we treat each node as a "super-item"; including a node in a test amounts to including all of the items in the corresponding group G ( ) j . While this may appear to naturally lead to an adaptive algorithm, we can in fact perform all of the tests non-adaptively.

If we were to test nodes at the root or the early levels, they would almost all return positive, and hence not convey significant information. We therefore let the algorithm start at the level min = log 2 k, and we consider the following test design:

• For each = log 2 k, . . . , log 2 n − 1, form a sequence of Ck tests (for some C > 0 to be selected later), and for each j = 1, . . . , 2 , choose a single such test uniformly at random, and place all items from G ( ) j into that test.

• For the final level = log 2 n, each G ( ) j = {j} is a singleton. In this case, we form C log k sequences of 2k tests (for some C > 0). For each item, and each of the C log k sequences of tests, we place the item in one of the 2k corresponding tests, chosen uniformly at random.

This creates a total of t = Ck log 2 n k + 2C k log k = O(k log n) tests. Upon observing the t non-adaptive test outcomes, the decoder forms an estimate S of the defective set via the following procedure:

• Iterate the following for = log 2 k, . . . , log 2 n − 1:

-For each group G ∈ G ( ) , check whether the single test corresponding to that group is positive or negative. If positive, then add both children of G (see Figure 1 ) to G ( +1) .

• Let the estimate S of the defective set be the (singleton) elements of G (log 2 n) that are not included in any negative test among the 2C k log k tests at the final level.

Comparisons with existing methods Our algorithm is distinct from existing sublinear-time nonadaptive group testing algorithms, which are predominantly based on code concatenation [31, 37] or related methods that encode item indices' binary representations directly into the test matrix [8, 10, 34] . In fact, in the context of group testing, our approach is perhaps most reminiscent of the adaptive algorithm of Hwang [29] (see also [4, 20] ), which identifies one defective at a time using binary splitting, removing each defective from consideration after it is identified. By keeping track of the multiple defective nodes simultaneously and allowing a small number of false positives up to the final level, we are able to exploit similar ideas without requiring adaptivity.

Beyond group testing and binary splitting, this recursive tree-structured approach is also reminiscent of ideas used in sketching algorithms, such as dyadic tree recovery for count-min sketch [18] . Our particular approach-maintaining a superset at each level, and relying on a lack of false negatives-is most similar to the pyramidal reconstruction method for compressive sensing under the earth mover's distance [32] .

A nearly identical algorithm to ours was given independently in the concurrent work of [13] , with similar theoretical guarantees. In addition, [13] observes that since the total number of non-discarded nodes in the algorithm is O k log n k with overwhelming probability (see Lemma 5 below), one can take a union bound over the n k possible defective sets to attain list recovery in the combinatorial (for-all) setting. This idea allows the authors of [13] to attain a variety of other results, including in the related problems of heavy hitters and compressive sensing. In the context of probabilistic (for-each) group testing, some slight advantages of our analysis include (i) proving that the first batch of tests leads to O(k)-size list recovery rather than O k log n k -size, thus circumventing the need for a third batch of tests, and (ii) only requiring O(log k)wise independence in our low-storage variant based on hashing (see Section 3), rather than O k log n k -wise independence (albeit at the expense of a higher error probability).

In the following, we provide the formal version of Main Result 1. Here and subsequently, we assume a word-RAM model of computation; for instance, with n items and t tests, it takes constant time to read a single integer in {1, . . . , n} from memory, perform arithmetic operations on such integers, fetch a single test outcome indexed by {1, . . . , t}, and so on. In addition, the number of tests scales as O(k log n). We note that the success probability approaches one as n → ∞ in any asymptotic regime satisfying k = ω(1), but not in the regime k = O(1); the same is true in the existing works listed in Table 1 , with the exception of [9] . In addition, it is straightforward to improve the success probability to 1 − e −Ω(k) − O(n −c ) by using O(log n) (rather than O(log k)) sequences of 2k tests at the final level.

Theorem 1 is proved in the remainder of the section. We emphasize that our focus is on scaling laws, and we make no significant effort to optimize the underlying constant factors.

Throughout the analysis, the defective set S will be fixed but otherwise arbitrary, and we will condition on fixed placements of the defective items into tests (and hence, fixed test outcomes). The test placements of the non-defective items are independent of those of the defectives, and our analysis will hold regardless of which particular tests the defectives were placed in. We use P[· | T S ] to represent this conditioning, and we refer to T S as the defective test placements. In addition, for the tree illustrated in Figure 1 , we refer to nodes containing defective items as defective nodes, to all other nodes as non-defective nodes, and to the set of defective nodes as the defective (sub-)tree. 4 We begin with the following simple lemma. Lemma 1. (Probabilities of Non-Defectives Being in Positive Tests) Under the test design described in Section 2.1, the following holds at any given level = log 2 k, . . . , log 2 n − 1: Conditioned on any defective test placements T S , any given non-defective node at level has probability at most 1 C of being placed in a positive test.

Proof. Since there are k defective items, at most k nodes at a given level can be defective, and since each node is placed in a single test, at most k tests out of the Ck tests at the given level can be positive. Since the test placements are independent and uniform, it follows that for any non-defective node, the probability of being in a positive test is at most 1 C .

In view of this lemma, when starting at any non-defective child of any given defective node (or alternatively, starting at a non-defective node at level min ), we can view any further branches down the non-defective sub-tree as "continuing" (i.e., the two children remain "possibly defective") with probability at most 1 C . Hence, we have the following. We will use the preceding lemmas to control the following two quantities:

• N total , the total number of non-defective nodes that are reached in the sense of Lemma 2;

• N leaf , the number of non-defective leaf nodes that are reached, and thus are still considered possibly defective by the final level.

It will be useful to upper bound N total for the purpose of controlling the overall decoding time, and to upper bound N leaf for the purpose of controlling the number of items considered at the final level.

We first present two lemmas bounding the averages of N total and N leaf , and then establish high-probability bounds. 4 Since we start at level min = log 2 k, this could more precisely be considered as a forest. (1)

Proof. Since the tree is binary, each defective node can have at most 2 i non-defective descendants appearing exactly i levels further down the tree; such descendants correspond to ∆ = i − 1 in Lemma 2. Since there are at most k log 2 n k defective nodes, it follows that there are at most k log 2 n k 2 ∆+1 non-defective nodes with ∆ non-defective ancestors and at least one defective ancestor. Similarly, there are at most k non-defective nodes at level min = log 2 k, each of which has at most 2 ∆ non-defective nodes appearing ∆ levels later.

Since Lemma 2 demonstrates a probability 1 C ∆ of being reached for a given number ∆ of non-defective ancestors, it follows that

Hence, the assumption C ≥ 4 gives

where we used 

Proof. Again using the fact that each defective node can have at most 2 i descendants appearing i levels further down the tree, we find that there are at most k2 ∆+1 leaf nodes with ∆ non-defective ancestors and at least one defective ancestor. In addition, a leaf having only non-defective ancestors corresponds to ∆ = log 2 n k in Lemma 2 (since min = log 2 k), and to handle this case, we trivially upper bound he number of leaves by n. Hence, for C ≥ 4, we have similarly to (3) that

In this subsection, we prove the following.

Lemma 5. (High-Probability Bound on N total ) For any C ≥ 16, conditioned on any defective test placements

To prove this result, we make use of Lemmas 1 and 3, along with the following auxiliary result written in generic notation. Proof. We make use of branching process theory [24, Ch. XII], in particular noting that N equals the total progeny [21] when the initial population size is 1 (i.e., the root) and the distribution of the number of children per node is given by

The results we use from branching process theory are expressed in terms of the generative function M X (s) = E[s X ], which is given by

It is evident in our case that N < ∞ with probability one provided that q < 1 2 , and one way to formally prove this is to utilize the general result that the extinction probability P[N < ∞] equals one provided that the smallest root of s = M X (s) is s = 1 [24, Sec. XII.4].

We utilize an exact expression for the distribution of N for general branching processes [21] (specialized to the case that the initial population size is one):

where m 

Substituting our expression (7) for M X (s) on the left-hand side, we find that (M X (s)) n = (1 − q) + qs 2 n , which equals 

where we applied n n−1 2 ≤ 2 n = 2 · 2 n−1 and (1 − q) n+1 2 ≤ 1.

Substituting (11) into (8), we obtain

This implies P[N = n] ≤ 2 −(n−1) when q ≤ 1 16 and n ≥ 2, and the same trivially holds when n = 1.

The condition P[N = n] ≤ 2 −(n−1) in Lemma 6 implies that N is a sub-exponential random variable, and the same trivially follows for a branching process that only runs up to a certain depth (number of generations).

In the group testing setup of Lemma 5, we are adding together O k log n k independent copies of such random variables (each corresponding to a different non-defective sub-tree) to get N total . As a result, we can apply a standard concentration bound for sums of independent sub-exponential random variables [43, Prop. 5.16] to obtain

from which Lemma 5 follows by setting t = Θ k log 2 n k and using E[N total | T S ] = O k log 2 n k (see Lemma 3). The condition C ≥ 16 coincides with q ≤ 1 16 in Lemma 6.

In this subsection, we prove the following. We again use Lemma 1, along with the following auxiliary results written in generic notation. Proof. We use a proof by induction. The base case is h = 1, in which case we have P[N h > 2] = 0, P[N h = 2] = 1 q 3 , and P[N h ≥ 1] ≤ 2 q 2 by the union bound. These bounds satisfy the claim of the lemma due to the assumption q ≤ 1 12 . Now fix h ≥ 2 and suppose that the claim is true for height h − 1. Let L and R be the number of leaf nodes reached in the left and right sub-trees of the root, and observe that

Applying the induction hypothesis, we find that the first two terms are at most q4 −(h−1+t) = 4q · 4 −(h+t) ,

where the multiplications by q correspond to the root node being marked as 1. Substituting back into (15) gives

We may assume that t ≤ 2 h , since for t > 2 h we trivially have P[N h ≥ t] = 0. Hence, the above bound simplifies to

since h ≥ 2 implies 2 −h ≤ 1 4 , and we have assumed q ≤ 1 12 . We now consider the following decomposition of N leaf :

where N leaf counts the reached non-defective leaf nodes having at least one defective ancestor, and N leaf counts the reached non-defective leaf nodes having all non-defective ancestors. In the case of a single defective item (i.e., k = 1), we claim that N leaf has the same distribution as 2N , with N given in Lemma 9

for a suitably-chosen value of h max and q = 1 C . To see this, we identify the leaf nodes in Lemma 9 with nodes at the second-last level of the tree illustrated in Figure 1 , and observe that the factor of 2 arises since every such node produces two children at the final level (hence contributing to N leaf ) when placed in a positive test.

In the case of k defective items, some care is needed, as the relevant sets of leaves associated with the k defective paths may overlap, potentially creating complicated dependencies between the associated random variables. However, if we take the definition of N in Lemma 9 and remove some leaves from the count, the Thus, by (18) , N leaf is the sum of at most 2k independent sub-exponential random variables. Again applying a standard concentration bound [43, Prop. 5.16] , it follows that

from which Lemma 7 follows upon setting t = Θ(k) and using the fact that E[N leaf | T S ] = O(k) (see Lemma 4).

Recall that at the final level, we perform C log k independent sequences of 2k tests, with each item being randomly placed in one test in each sequence. We study the error probability conditioned on the high-

For a given non-defective item and a given sequence of 2k tests, the probability of colliding with any defective item is at most 1 2 , similarly to Lemma 1. Due to the C log k repetitions, for any fixed c > 0, there exists a choice of C yielding O(k −c ) probability of a given non-defective appearing only in positive tests.

By a union bound over the N leaf = O(k) non-defectives at the final level, we find that the estimate S equals S with (conditional) probability 1 − O(k 1−c ).

The claims of Theorem 1 are established as follows:

• Number of tests: As stated in Section 2.1, the number of tests is t = Ck log 2 n k + 2C k log k, which behaves as O k log n k + k log k = O(k log n).

• Error probability: The concentration bounds on N leaf and N total (see Lemmas 5 and 7) hold with probability 1 − e −Ω(k) and 1 − e −Ω(k log n k ) respectively, and we treat their complements as error events. • Storage: At the -th level, we need to store 2 integers indicating the test associated with each of the 2 nodes. Hence, excluding the last level, we need to store 

A notable weakness of Theorem 1 is that the storage required at the decoder is higher than linear in the number of items. In this section, we present a variant of our algorithm with considerably lower storage that attains similar guarantees to Theorem 1. A second modification to the algorithm is that in order to attain the behavior O(k −c ) in the error probability similarly to Theorem 1, we consider the use of C ≥ 1 independent repetitions at each level = min , . . . , log 2 n − 1, in the same way that we already used repetitions at the final level. This means that at each level, there are C sequences of Ck tests (each with a different and independent hash function), and a node is only considered to be possibly defective at a given level if all of its associated C tests are positive.

Remark. This idea of using low-storage hash functions is reminiscent of the Bloom filter data structure [7] .

A direct approach to transferring Bloom filters to group testing is to perform L = O(log n) hashes of each item into one of t = O(k log n) tests, and then estimate the defective set to be the set of items only included in positive tests [4, Sec. 1.7] . By checking the L test outcomes associated with each item, the defective set can be identified with low storage (depending on the hash family properties) under the preceding scaling laws. However, a drawback of this direct approach is that checking all items separately takes Ω(n) time.

Our algorithm circumvents this via the binary splitting approach.

With the above-described modifications to the algorithm, we have the following counterpart to Theorem 1, which formalizes and generalizes Main Result 2. • The algorithm uses O(k log n + S hash log n) bits of storage, where S hash is the number of bits of storage required for one hash function.

In addition, the number of tests scales as O(k log n).

We briefly discuss some explicit values that can be attained for T hash and S hash . Supposing that n, k, and C are powers of two, we can adopt the classical approach of Wegman and Carter [44] and consider a random polynomial over the finite field GF(2 m ), where m ∈ {log 2 k, . . . , log 2 n} (depending on the level). In this case, one attains r-wise independence while storing r elements of GF(2 m ) (or O(r log n) bits), and performing O(r) additions and multiplications in GF(2 m ) to evaluate the hash. As a result, with r = Θ(log k), we get

under the assumption that operations in GF(2 m ) can be performed in constant time. Hence, Theorem 2

gives O(k log k · log n) decoding time and O(k log n + log k · log 2 n) storage. Different trade-offs can also be attained using more recent hash families that can attain r-wise independence with an evaluation time significantly less than r [40, 41] . In the remainder of the section, we provide the proof of Theorem 2.

We first study the case C = 1 (i.e., no repetitions), as the case C > 1 will then follow easily.

Recall that the algorithm maintains an estimate of the possibly defective (PD) set at each level. We will give conditions under which the size of this set remains at O(k) throughout the course of the algorithm. For = min = log 2 k, we trivially have at most k ≤ 4k PD items. We will use an induction argument to show that every level has at most 4k PD items, with high probability.

Consider two non-defective nodes indexed by u, v at a given level having k ≤ k defective nodes, let D u , D v denote the respective events of hashing into a test containing one or more defectives, and let D u , D v be the corresponding indicator random variables. The dependence of these quantities on is left implicit. We condition on all of the test placements performed at the earlier levels, accordingly writing E [·] and Var [·] for the conditional expectation and conditional variance. In accordance with the above induction idea, we assume that there are at most 4k PD nodes at level . 4k PD nodes at level , then we have the following when C = 1 and C ≥ 8:

where the sums are over all non-defective PD nodes at the -th level, and c var > 0 is a universal constant.

The proof is given in Appendix B. Given this result, we easily deduce the following.

Lemma 11. For C = 1 and C ≥ 8, conditioned on the -th level having at most 4k possibly defective (PD) nodes, the same is true at the ( + 1)-th level with probability 1 − O 1 k .

Proof. Among the PD nodes at the -th level, at most k are defective, amounting to at most 2k children at the next level. By Lemma 10 and Chebyshev's inequality, with probability 1 − O 1 k , at most k non-defective nodes are marked as PD, thus also amount to at most 2k additional children at the next level, for a total of 4k.

At the first level = log 2 k, we trivially have k ≤ 4k possibly defective (PD) nodes. For C = 1, using Lemma 11 and an induction argument, the same follows for all levels simultaneously with probability at least 1 − O(k −1 log n). For C > 1, we note that since we have C repetitions at each level and only keep the nodes whose tests are all positive, the 1 − O(k −1 ) behavior becomes 1 − O(k − C ) due to the independence of the repetitions. Hence, the expression 1 − O(k −1 log n) for C = 1 generalizes to 1 − O k − C log n . The analysis of the final level in Section 2.3.4 did not rely on h(·) being a fully independent hash function, but rather, only relied on a collision probability of 1 2k between any two given items. Since this condition still holds for any pairwise (or higher) independent hash family, we immediately deduce the same conclusion: Conditioned on the final level having O(k) nodes marked as possibly defective, and by choosing C appropriately in the algorithm description, we attain O(k 1−c ) error probability at this level for any fixed c > 0.

Combining the above and setting C = c and c = 1 + c, we attain the desired scaling O(k −c log n) in the theorem statement.

The remaining claims of Theorem 2 are established as follows:

• Number of tests: The number of tests is the same as in the fully independent case, possibly with a modified implied constant if C > 1 and/or a different choice of C is used. 

We have presented a novel non-adaptive group testing algorithm ensuring high-probability (for-each) recovery with O(k log n) scaling in both the number of tests and decoding time. In addition, we presented a lowstorage variant with similar guarantees depending on the hash family used. An immediate open question for this variant is whether similar guarantees hold for O(1)-wise independent hash families. In addition, even for the fully independent version, it would be of significant interest to develop a variant that is robust to random noise in the test outcomes (see Footnote 2 on Page 4). a given bundle, then its (log 2 n)-bit description is encoded into the first log 2 n tests (i.e., the item is included in the test if and only if its bit description contains a 1 at the corresponding location), and its bit-wise complement is encoded into the last log 2 n tests. The following decoding procedure ensures the identification of any defective item for which there exists a bundle in which it is included without any other defective items:

• For each bundle, check whether the first log 2 n test outcomes equal the bit-wise negation of the second log 2 n outcomes.

• If so, add the item with bit representation given by the first log 2 n outcomes into the defective set estimate.

Due to the first step, the second step will never erroneously be performed on a bundle without defective items, nor on a bundle with multiple defective items.

In [34] , a decoding time of O(k log k · log n) is stated under the assumption that reading the 2 log 2 n bits takes O(log n) time. However, if the associated 2 log 2 n tests are stored in memory as two "words" of length We also note that SAFFRON only requires O(k log k · log n) bits of storage, amounting to negligible storage overhead beyond the test outcomes themselves. This is because the only item indices stored are those added to the estimate of the defective set, and there are at most k such indices (or k log 2 n bits) due to the fact that SAFFRON makes no false positives.

For ease of notation, we leave the subscripts (·) implicit throughout the proof, but the associated conditioning is understood to apply to all probabilities, expectations, variance terms, and so on.

We first prove (21) . The event D u occurs if u is hashed into the same bin as any of the k ≤ k defective nodes. Since we are hashing into {1, . . . , Ck} and the hash family is (at least) pairwise independent, each collision occurs with probability 1 Ck . Hence, by the union bound, u is in a positive test with probability at most 1 C , and (21) follows from the assumption that there are at most 4k PD nodes and C ≥ 8.

As for (22), we first characterize Cov[D u , D v ], writing

We proceed by bounding P[D u ] (the same bound holds for P[D v ]) and P[D u ∪ D v ] separately.

Probability of the individual event Fix a non-defective node u. Let h(·) denote the random hash function with output values in {1, . . . , Ck}, and for each defective node indexed by i ∈ {1, . . . , k } (where k is the total number of defective nodes at the level under consideration), let B i be the "bad" event that h(i) = h(u). We apply the inclusion-exclusion principle, which is written in terms of the following quantities for j = 1, . . . , k :

If the hash function is (j + 1)-wise independent, this simplifies to

Hence, if the hash function is (j max +1)-wise independent for some j max , then the inclusion-exclusion principle 

for odd-valued j max , and the reverse inequality for even-valued j max . Using the fact that 

The final term can then be bounded as follows in absolute value:

where (33) uses k j ≤ (k ) j and k ≤ k, and (34) applies the geometric series formula. Assuming C ≥ 2, we can further upper bound the above expression by (1/C) jmax , and hence by any target value δ 0 provided that j max ≥ log C 1 δ0 . Recall also that (31) is reversed for even-valued j max , so loosening the preceding requirement to j max ≥ log C 1 δ0 + 1 gives

Since u is arbitrary, the same bound also holds for P[D v ].

Probability of the union of two events We can decompose P[D u ∪ D v ] as follows:

Hence, we focus on the case h(u) = h(v) in the following. Similar to the above, let B i be the "bad" event that h(i) ∈ {h(u), h(v)}, and define

If the hash function is (j + 2)-wise independent, this simplifies to

where the factor of two comes from the possibility of colliding with either u or v. Following the same argument as above, we find that if (i) j max ≥ log C/2 1 δ0 + 1, (ii) C ≥ 4, and (iii) the hash function is (j max + 2)-wise independent, then the following analog of (35) holds:

Combining and simplifying Setting δ 0 = 1 k and combining the above findings, we deduce that for a Θ(log k)-wise independent hash,

The idea in the following is to approximate 1 − ν Ck ≈ e − 1 Ck for ν = 1, 2, and substitute into (25) . To make this more precise, we use the fact that k ≤ k to write

Applying a similar argument to 1 − 2 Ck k and substituting into (25) , we obtain

since the first three terms cancel upon expanding the square. The proof is concluded by writing 

Individual testing is optimal for nonadaptive group testing in the linear regime

Group testing algorithms: Bounds and simulations

The capacity of Bernoulli nonadaptive group testing

Group testing: An information theory perspective

Boolean compressed sensing and noisy group testing

The capacity of adaptive group testing

Space/time trade-offs in hash coding with allowable errors

Cross-sender bit-mixing coding

Sublinear-time non-adaptive group testing with O(k log n) tests via bit-mixing coding

Efficient algorithms for noisy group testing

Non-adaptive group testing: Explicit bounds and novel algorithms

Noise-resilient group testing: Limitations and constructions

Combinatorial group testing and sparse recovery schemes with nearoptimal decoding time

Pattern matching with don't cares and few errors

Information-theoretic and algorithmic thresholds for group testing

Optimal non-adaptive group testing

What's hot and what's not: Tracking most frequent items dynamically

An improved data stream summary: the count-min sketch and its applications

The detection of defective members of large populations

Combinatorial group testing and its applications

The total progeny in a branching process and a related random walk

A survey of superimposed code theory

Bounds on the rate of superimposed codes

An introduction to probability theory and its applications

Unbounded contention resolution in multiple-access channels

One sketch for all: Fast algorithms for compressed sensing

Group testing and sparse signal recovery

Sample Pooling as a Strategy to Detect Community Transmission of SARS-CoV-2

A method for detecting all defective members in a population by group testing

On the optimality of the Kautz-Singleton construction in probabilistic group testing

Efficiently decodable non-adaptive group testing

K-median clustering, model-based compressive sensing, and sparse recovery for earth mover distance

Performance of group testing algorithms with near-constant tests-per-item

SAFFRON: A fast, efficient, and robust framework for group testing based on sparse-graph codes

Screening designs for non-symmetric response function

The separating property of random matrices

Efficiently decodable error-correcting list disjunct matrices and applications

Explicit nonadaptive combinatorial group testing schemes

Phase transitions in group testing

On universal classes of fast high performance hash functions, their time-space tradeoff, and their applications

Fast and powerful hashing using tabulation

Group testing for SARS-CoV-2 allows for up to 10-fold efficiency increase across realistic scenarios and testing strategies

Introduction to the non-asymptotic analysis of random matrices

New hash functions and their use in authentication and set equality

Evaluation of COVID-19 RT-qPCR test in multi-sample pools

While the SAFFRON algorithm [34] is based on sparse-graph codes, we find it most instructive to compare against the simplified singleton-only version [4, Sec. 5.4] , as the more sophisticated version does not attain better scaling laws (though it may attain better constant factors).Singleton-only SAFFRON is briefly outlined as follows. One forms O(k log k) "bundles" of tests of size