1 Introduction↩︎

The group testing problem, in which one seeks to identify a subset of “defective” items using pooled tests, has been widely studied since its introduction in the 1940s, and has far-reaching applications including medical testing [1], DNA testing [2], [3], database systems [4], communication protocols [5], [6], and more. The majority of attention has been paid to the standard binary “OR” model, in which a test outcome is positive if and only if it includes at least one defective item, but a number of alternative models have also been proposed, including the following:

• In quantitative group testing (QGT) [7], [8], the test outcome reveals the number of defectives in the test, and is thus a non-binary outcome;

• In semi-quantitative group testing (SQGT) [9], [10], the test outcome can be viewed as a quantized form of the QGT outcome, so that the outcome reveals a certain range that the number of defectives lies in (but not the exact value);

• In the simplest form of threshold group testing (TGT) [11]–[13], the test outcome is again binary, and indicates whether or not the number of defectives is greater than or equal to a certain threshold \(\gamma\); setting \(\gamma=1\) gives regular group testing.

In this paper, we study a setting that builds on TGT but is new to the best of our knowledge: For each test, we can not only select which items are included in the test, but also select the threshold \(\gamma\) such that the test outcome is \(Y = \mathbb{1}\{ \text{\#defectives in test} \ge \gamma\}\) (subject to suitable constraints such as \(\gamma \le \gamma_{\max}\)). We call this problem group testing with selectable thresholds (GT-ST).

From an application viewpoint, this setting is potentially relevant to scenarios where the testing device has a “sensitivity parameter” that dictates how many defectives are required to produce a positive outcome, though we are starting with an idealized theoretical model in which the threshold can be specified exactly without noise. From a theoretical viewpoint, GT-ST is a natural generalization of TGT, and its study provides insight on what kinds of 1-bit test outcomes are useful, and how the flexibility of selectable thresholds can simplify algorithm design.

We proceed to describe the problem formally, and then outline the related work and our contributions.

1.1 Problem Setup↩︎

There are \(n\) items, among which some subset \(S \subseteq[n] \mathrel{\vcenter{:}}= \{1,\dotsc,n\}\) of size \(|S|=k\) is defective. We focus on the widely-studied sublinear sparsity regime in which \(k = \Theta(n^{\theta})\) for some \(\theta \in (0,1)\). The number of tests is denoted by \(T\), and the \(t\)-th test is specified by an indicator vector \(x_t\in\{0,1\}^n\), where an entry of 1 indicates an item being included. The test outcome (described below) is denoted by \(y_t \in \{0,1\}\), and we collect the test vectors into a matrix \(\mathbf{X}\in \{0,1\}^{T \times n}\) and the test outcomes into a vector \(\mathbf{y}\in \{0,1\}^T\). We let \(\psi_t=\sum_{i\in S}x_{ti}\) denote the number of defectives in test \(t\).

In standard noiseless group testing (GT), we observe \(y_t=\mathbb{1}\{\psi_t\ge 1\}\). In noiseless threshold group testing (TGT), this generalizes to \(y_t=\mathbb{1}\{\psi_t\ge \gamma\}\) for some fixed threshold \(\gamma\). In this paper, we are interested in the following variant:

• Each test is specified not only by which items are included (i.e., \(x_t\in\{0,1\}^n\)), but also by a choice of a positive integer threshold \(\gamma^{(t)}\). Unless stated otherwise, we assume that the threshold is subject to a constraint of the form \(\gamma^{(t)} \le \gamma_{\max}\) for some maximum value \(\gamma_{\max}\).

• The corresponding test result is \(y_t=\mathbb{1}\{\psi_t\ge \gamma^{(t)}\}\).

We are interested in conditions under which this added flexibility can help in designing algorithms, e.g., by utilizing known group testing methods (with \(\gamma^{(t)} = 1\)) and combining them with higher-threshold tests.

In an adaptive testing strategy, each test (including its choice of threshold) may be designed based on previous outcomes, whereas in a non-adaptive testing strategy, all tests must be chosen in advance. For reasons we will mention shortly, we will focus entirely on non-adaptive strategies. Given \((\mathbf{X},\mathbf{y})\), a decoding algorithm produces an estimate \(\hat{S}\) of \(S\), and the error probability is given by \[P_e \mathrel{\vcenter{:}}= \Pr(\hat{S} \ne S),\] where the randomness is over a uniformly random defective set \(S\) of size \(k\), as well as any randomness used in the test design or decoding rule.

Before proceeding, we make a simple observation that the well-known counting bound remains true in our setting, as we formally state in the following.

Motivated by this result and the extensive developments in standard GT [15], we adopt the convention of measuring the number of tests using the rate: A sequence of strategies (indexed by \(n\)) is said to achieve rate \(R\) if it holds that \(P_e \to 0\) and \[\liminf_{n \to \infty} \frac{\log_2 {n \choose k}}{T} \ge R.\] In other words, the number of tests is at most \(\frac{1}{R} \log_2 {n \choose k}\) up to lower-order asymptotic terms (or equivalently \(\frac{1}{R} k \log_2 \frac{n}{k}\) since \(k = o(n)\)), and \(R\) represents the amount of information learned per test. The counting bound reveals that the rate can never exceed 1.

In the rest of the paper, we focus entirely on non-adaptive strategies, in which all tests must be decided in advance. For adaptive strategies, there is little to be gained, since well-known standard group testing methods asymptotically match the counting bound, and they can still be used in our setting as long as the threshold \(\gamma^{(t)} = 1\) is allowed. We highlight the following two test designs from the standard GT literature, which we will use in certain subroutines in our own algorithms.

Notation. The function \(\log(\cdot)\) has base \(e\), and we use the standard asymptotic notation \(O(\cdot)\), \(o(\cdot)\), \(\Omega(\cdot)\), \(\omega(\cdot)\), and \(\Theta(\cdot)\), often with the implicit understanding of the implied constants being non-negative. For two real-valued random variables \(U,V\) we use the notation \(U \preceq_{\rm st}V\) to mean that \(U\) is stochastically dominated by \(V\), i.e., \(\Pr(U \ge x) \le \Pr(V \ge x)\) for all \(x \in \mathbb{R}\) (and thus \(V\) is “larger” than \(U\) in a probabilistic sense).

1.2 Related work↩︎

Standard group testing. The information-theoretic and algorithmic limits of (noiseless) standard GT are now very well-understood; we provide a brief summary here, and refer the reader to [15] for a detailed overview. Some of the main milestones included rates of simple algorithms [16], information-theoretic achievability [17], improved rates via near-constant column weight designs [18], [19], and finally, optimal rates [20] (along with a polynomial-time strategy based on spatial coupling). We highlight two prominent standard GT algorithms (e.g., see [15]) that we will use as subroutines:

• The Combinatorial Orthogonal Matching Pursuit (COMP) algorithm declares all items in negative tests as non-defective, and the rest as defective.

• The Definite Defectives (DD) algorithm first forms the possibly defective (PD) set as the set of items appearing in no negative tests. It then declares an item as defective if it is PD and lies in at least one test with no other PD items, and declares the item as non-defective otherwise.

The optimal rates of standard GT with approximate recovery were also established in [17], [21], with a two-sided error guarantee allowing both \(o(k)\) false positives and \(o(k)\) false negatives. More relevant to our work is the recent work [22] studying one-sided criteria. Specifically, they established the optimal rates in the case of either \(o(k)\) false positives (SUPERSET) or \(o(k)\) false negatives (SUBSET), but not both. We will use their results for the SUBSET problem as a stepping stone towards some of our GT-ST results.

Threshold group testing. An early mathematical study of threshold group testing (TGT) was given by Damaschke [11]. The model therein was more general than that of Section 1.1 in that it allowed a gap: For some parameters \((\ell,u)\), the test result is always \(0\) with up to \(\ell\) defectives, always \(1\) with at least \(u\) defectives, and is arbitrary otherwise. Exact recovery turns out to be impossible when the “gap” \(g = u-\ell-1\) is positive, but one can still attain recovery to within \(g\) false positives and \(g\) false negatives.

Follow-up works on TGT include [23]–[25] for the setting with a gap, and [26]–[28] for the gap-free setting. All of the preceding works focus on zero-error (combinatorial) recovery, meaning that recovery must be deterministically guaranteed for all defective sets of a given size. Moreover, their focus is on scaling laws rather than precise constants. Thus, their settings and results are not comparable to ours, and we avoid going into significant detail.

Our focus is on small-error (probabilistic) recovery, allowing \(o(1)\) error probability with respect to a random defective set and/or a random test design. Threshold GT has historically received less attention in such settings, with a notable exception being the work of Laarhoven [29] providing exact threshold in the very sparse regime \(k = O(1)\) (which is known to be significantly simpler than the general sparse regime \(k = \Theta(n^{\theta})\)). However, two highly relevant papers very recently arose in concurrent work, which we now discuss in detail.

Comparison to concurrent work. In the late stages of our work, two closely related papers on (noiseless) threshold group testing appeared: The work of van der Hofstad et al. [30] establishes the exact information-theoretic limits of the NCC design (subject to a certain analytic conjecture holding for \(\gamma \ge 3\)), and the work of Coja-Oghlan et al. [31] establishes that the same rate can be achieved with polynomial-time decoding under a spatially coupled design (without needing the analytic conjecture). Thus, these works on TGT provide precise counterparts to standard GT results from [19] and [20] respectively. While there is some clear overlap with our work, we highlight the following key aspects in which our work differs:

• We introduce the selectable threshold setting, whereas [30], [31] focus on the case of a fixed non-selectable threshold.

• Within our setting, we propose an approach that is conceptually simple, easy to analyze (though sometimes relying on existing results), and can be computationally efficient. The idea is to identify most of the defectives using standard GT tests, and then resolve the remaining uncertainty via tests that use the highest threshold. While the resulting rates are not as precise as [30], [31], their simplicity and connections to the more well-studied standard GT problem make them potentially desirable.

• We establish a converse that matches that of [30] but holds in greater generality. Specifically, our converse holds even with selectable thresholds, and more importantly, even within a class of deterministic designs, rather than only the random NCC design of Definition 2. (We show that under the NCC design, our deterministic conditions hold with high probability.) This level of generality also leads to largely distinct proof details, though still following the same high-level idea of identifying “uninformative” tests.

1.3 Contributions↩︎

Our main contributions are outlined as follows:

• We introduce the GT-ST problem, as outlined above.

• We provide various algorithms based on first finding a near-complete subset of defectives using standard group testing queries and then resolving the remaining by additional tests that use \(\gamma^{(t)} = \gamma_{\max}\):

  • When the first step achieves the optimal threshold for the SUBSET problem [22] (albeit only currently proved for a computationally inefficient method), we establish an achievable rate that approaches 1 as \(\gamma_{\max}\) increases (with \(O\big(\frac{1}{\sqrt{\gamma_{\max}}}\big)\) convergence speed), thus approaching the counting bound.

  • When the first step instead uses a combination of the simple and computationally efficient COMP and DD algorithms [15], we obtain an achievable rate for the finite \(\gamma_{\max}\) setting, and observe that it can be strictly higher than the case \(\gamma_{\max} = 1\) (corresponding to standard group testing).

• Beyond the simple counting bound, we establish a refined converse for the finite \(\gamma_{\max}\) under suitable regularity conditions on the test matrix. Among other things, this establishes that our achievable number of tests is tight under these regularity conditions in the dense limit \(\theta \to 1\), albeit with gaps remaining for \(\theta < 1\). As noted above, this converse generalizes the converse from concurrent work [30], which was proved therein for TGT under the random NCC design.

For the fixed-\(\gamma_{\max}\) regime, an example rate plot (with \(\gamma_{\max} = 10\)) is shown in Figure 1, and demonstrates two notable features: (i) As \(\theta \to 1\), the achievability and converse match in the sense of having a matching slope (viewed differently, the bounds match asymptotically in terms of the ratio \(\frac{\#{\rm tests}}{k \log k}\), whereas the “inverse rate” \(\frac{\#{\rm tests}}{k \log \frac{n}{k}}\) approaches \(\infty\)), and (ii) For \(\theta\) sufficiently close to 1, the achievability curve is strictly higher than the optimal threshold for standard group testing, thus showing that (selectable) threshold queries are strictly more powerful.

2 Achievability Results↩︎

2.1 Warm-Up: Stronger Query Models↩︎

In this section, we discuss more general 1-bit models, as they will provide useful insights that we can build on. We broadly refer to a “query” as any yes/no question about a given test, e.g., our model in Section 1.1 is based on threshold queries of the form “are there at least \(\gamma^{(t)}\) defectives in the test?”.

2.1.1 General 1-bit Queries↩︎

We first note that the counting bound (Theorem 1) applies for arbitrary 1-bit queries; any group testing strategy whose error probability is bounded away from one as \(n \to \infty\) must have a number of tests \(T\) satisfying \(T \ge (1-\eta) \log_2 {n \choose k}\), where \(\eta > 0\) is arbitrarily small.

General 1-bit queries, in which \(y_t\) is an arbitrary 1-bit function of \(\{ i \,:\, i \in S, x_{ti} = 1 \}\) are “too powerful” in the sense that they make the problem trivial to solve. Specifically, we can let the test include all items, in which case the preceding set becomes \(S\) itself, and then we can trivially ask queries of the following form: “Represent each \(S\) by a length-\(\log_2 {n \choose k}\) binary vector: Is the first bit 1? Is the second bit 1? (etc.)”. This trivially succeeds using \(\log_2 {n \choose k}\) 1-bit queries, and matches the counting bound.

To reduce the power of the 1-bit queries, a natural starting point is to require that they return a function of the number of defectives in the test (i.e., \(\psi_t\)). Group testing models satisfying this property are termed “only defects matter” in [15].

2.1.2 Two-Stage Template via Subset and Quantitative Queries↩︎

In this subsection, we momentarily suppose that we have access to a limited number of quantitative queries that return \(\psi_t\) itself, thus violating the condition of 1-bit queries. After this subsection, we will only consider 1-bit queries.

We propose a strategy that mostly makes standard (1-bit) group testing queries, and then makes a small number of quantitative queries. Accordingly, the tests are performed in two batches:

• Batch 1 (Subset). In this batch, we perform only standard group testing queries. We use these to run a non-adaptive routine Subset that returns \(\widehat{S}_1 \subseteq S\) of size \(|\widehat{S}_1| \ge k-k/\log^4 k\) (i.e., it misses at most \(k/\log^4 k\) defectives). This can be done with a number of tests meeting the counting bound [22].

• Batch 2 (Reduced GT). Design tests for a standard group testing problem with \(k/\log^4 k\) defectives, but instead of observing the standard results, observe the quantitative results (\(\psi_t\)). Subtract the contribution of items in \(\widehat{S}_1\) from each measurement, then change any non-zero result to \(1\) (i.e., an “OR” operation), so that the outcomes correspond to standard GT outcomes on the reduced defective set \(S \setminus \widehat{S}_1\). Run a standard GT decoder such as COMP or DD (see Section 1.2 for their descriptions) to recover the defectives that were not identified in batch 1.

Batch 2 then needs only \(O\big((k/\log^4 k)\log n\big) = o(k \log \frac{n}{k})\) tests, and the overall rate is \(1\). However, we would like to avoid the use of quantitative queries; we now give a simple variation for this purpose.

2.1.3 Adapting to Generalized 1-bit Queries↩︎

Observe that in batch 2 above, the test outcomes lie in \(\{0,1,\dotsc,k\}\). As a result, we can trivially adapt the above strategy to only use 1-bit queries by repeating each of batch 2’s test placements \(\log_2(k+1)\) times, but with each repetition using a different choice of 1-bit query, namely, one for each of the \(\log_2(k+1)\) bits in the binary expansion of \(\psi_t\) (or similarly with suitable rounding to an integer). This only increases the number of tests in batch 2 by an \(O(\log k)\) factor to a total of \(O\big((k/\log^3 k)\log n\big)\), and all tests are now 1-bit. Observe that the number of tests in batch 1 dominates, and so this strategy achieves a rate of \(1\).

2.1.4 Adapting to Unbounded Threshold Queries↩︎

To conclude this “warm-up” subsection, we adapt the above strategy to the case that only threshold queries are allowed but there are no constraints on the selectable threshold (i.e., \(\gamma_{\max} = \infty\), which is equivalent to \(\gamma_{\max} = k\)). We outline the relevant analysis below and defer the full details to Appendix 6.1.

A naive strategy would be to learn \(\psi_t\) by testing all thresholds \(\gamma \in \{1,2,\dotsc,k\}\), but this would require \(k\) queries to learn each value of \(\psi_t\). This can be reduced by noticing that the number of defectives (including those in \(\widehat{S}_1\)) in each test of batch 2 is \(\Theta\big( \log^4 k \big)\) with high probability; however, testing all thresholds \(\gamma \in \{1,2,\dotsc,\Theta(\log^4 k)\}\) would still lead to \(O(k \log n)\) tests in batch 2. The solution is to further narrow the required range using a concentration argument.

Specifically, consider a Bernoulli test design with inclusion probability \(p=\frac{\log^4 k}{k}\) so that \(\mu_\psi \mathrel{\vcenter{:}}= \mathbb{E}[\psi_t]=\log^4 k\). By the multiplicative Chernoff bound and a union bound over all tests in the second batch, it can be shown that the deviation of \(\psi_t\) from its mean \(\mu_\psi\) is at most \(\Theta(\log^{5/2}k)\) for all \(t\) with probability \(1-o(1)\). Hence one can emulate a quantitative result with only \(O(\log^{5/2} k)\) threshold queries per test, so the total scales as \[O\left(\frac{k}{\log^4 k}\log n\right)\times O(\log^{5/2} k)=o(k\log n).\] Thus, batch 1 again dominates, and we meet the counting bound. Formally, we have the following.

See Appendix 6.1 for a detailed proof of this result.

2.2 The Large \(\gamma_{\max}\) Limit↩︎

In this subsection, we seek to sharpen the understanding from Theorem 2 by studying the case that \(\gamma_{\max}\) is “bounded but large”. Specifically, we seek to understand how quickly the rate approaches 1 as \(\gamma_{\max} \to \infty\), where this limit is taken after having already taken \(n \to \infty\) with \(k = \Theta(n^{\theta})\). We outline the relevant analysis below and defer the full details to Appendix 6.2.

We adopt a similar strategy to the previous subsection, but with modified parameters so that \(\psi_t\) in batch 2 concentrates around \(\gamma_{\max} / 2\) rather than around \(\log^4 k\). In batch 1, we again apply Subset to identify \(k-k/\log^4 k\) defectives. In batch 2, we apply Bernoulli testing with inclusion probability \(p=\frac{\gamma_{\max}}{2k}\) and keep only those tests whose number of defectives lies in the interval \((\gamma^-, \gamma^+) \mathrel{\vcenter{:}}=(\frac{\gamma_{\max}}{2}-2\sqrt{\gamma_{\max}},\,\frac{\gamma_{\max}}{2}+2\sqrt{\gamma_{\max}})\) (see below for how this is detected). Similar to the case with unbounded \(\gamma_{\max}\), we repeat each test \(O(\sqrt{\gamma_{\max}})\) times by initially using threshold \(\lfloor \gamma^-\rfloor\), and repeating the test with incrementing thresholds until reaching \(\lceil \gamma^+ \rceil\). This allows us to learn \(\psi_t\) if it lies within \((\gamma^-, \gamma^+)\), or learn that \(\psi_t\) lies outside of the interval, in which case it is discarded. The multiplicative Chernoff bound (Lemma 3) implies that the probability of \(\psi_t\) falling outside of this interval is upper bounded by an absolute constant. Thus, the window captures a constant fraction of tests, so discarding the rest loses only a constant factor (with high probability).

Observe that the “residual” problem (with the Subset defectives removed) has up to \(\frac{k}{\log^4 k}\) unknown defectives and inclusion probability \(p = \frac{\gamma_{\max}}{2k}\). Using Bernoulli’s inequality, the probability of a specific test containing none of these defectives (which we term being residually negative) is lower bounded by \[\left(1-\frac{\gamma_{\max}}{2k}\right)^{k/\log^4 k} \geq 1-\frac{\gamma_{\max}}{2\log^4 k} = 1-o(1).\] Now let us momentarily assume that the remaining residually negative tests are quantitative (i.e., \(\psi_t\) is observed), and that there are \(T_2'\) such tests (among those that were not discarded). Then, we can apply the same steps as in Section 2.1.2 (i.e., subtract the contribution from \(\widehat{S}_1\), change non-zero tests to \(1\)) to convert it to a classical group testing problem. We can then recover the remaining defective items from these “converted” tests using these residually negative tests. A fixed non-defective fails to appear in any kept residually negative test with probability \(\big(1 - \frac{\gamma_{\max}}{2k}\big)^{T_2'} \leq \exp\big(-\frac{\gamma_{\max}}{2k}T_2'\big)\). Thus, if \(T_2'=\Theta\big(\frac{k\log n}{\gamma_{\max}}\big)\) with a large enough implied constant, then every non-defective will appear in at least one such negative test with probability \(1-o(1)\), implying successful recovery.

Each “quantitative test” corresponds to evaluating \(O(\sqrt{\gamma_{\max}})\) threshold queries (i.e., the above-mentioned interval length), and hence, the overall number of 1-bit queries (to non-discarded, residually negative tests) sufficient for accurate recovery is \[T''_2=\Theta\left(\frac{k\log n}{\sqrt{\gamma_{\max}}}\right). \label{eq:T295gamma95max}\tag{1}\] To ensure that there are \(T''_2\) non-discarded and residually negative 1-bit tests, we set the actual number of conducted tests to be \[\label{eq:actual95T} T_2 = \Theta(T''_2) = \Theta\left(\frac{k\log n}{\sqrt{\gamma_{\max}}}\right).\tag{2}\] Since a constant fraction of \(T_2\) will be discarded, and a further \(\gamma_{\max}/(2\log^4 k) = o(1)\) fraction will not be residually negative, we can set the implied constant in 2 sufficiently large to attain 1 with high probability (by binomial concentration). Adding the \(\big(k\log_2\frac{n}{k}\big)(1+o(1))\) tests from batch 1, we see that the rate attained is \(\big(1+O(\gamma_{\max}^{-1/2})\big)^{-1}=1-O(\gamma_{\max}^{-1/2})\). Formally, we have the following.

The detailed proof of this result can be found in Appendix 6.2.

2.3 The Finite \(\gamma_{\max}\) Regime↩︎

We now look at attaining a closer understanding when \(\gamma_{\max}\) is a fixed constant, starting with \(\gamma_{\max} = 2\). We outline the relevant analysis below and defer the full details to Appendix 6.3.

2.3.1 The Case \(\gamma_{\max}=2\)↩︎

We start with the case \(\gamma_{\max} = 2\), and again adopt a two-batch approach. This means that each test result can reveal one of four things: \(\psi_t = 0\), \(\psi_t \ge 1\), \(\psi_t \in \{0,1\}\), or \(\psi_t \ge 2\) (only the former two if \(\gamma = 1\), and only the latter two if \(\gamma = 2\)).

Different from before, we only use one threshold in each batch: \(\gamma = 1\) (i.e., standard GT) in batch 1, and \(\gamma = 2\) in batch 2. Throughout, we will adopt separate NCC designs (Definition 2) in each batch; in the first batch we set \(L_1 = \frac{T_1 \log 2}{k}\), and in the second we set \(L_2 = \frac{T_2\nu}{k}\) for some parameter \(\nu > 0\) that can be optimized.

Batch 1: In the first batch, we use the threshold \(\gamma^{(t)} = 1\) and adopt a design achieving rate \(\log 2\), so that \(T_1 = (\frac{1}{\log2} k\log_2(n/k)) (1 + o(1))\). By applying the approximate recovery versions of COMP and DD decoding, we can attain (with \(1-o(1)\) probability) a subset \(S_{\mathrm{DD}}\subseteq S\) of size \(k(1-o(1))\) and a superset \(S_{\mathrm{COMP}}\supseteq S\) of size \(k(1+ o(1))\) [22].

Batch 2: We use the threshold \(\gamma^{(t)} = 2\). For each \(i\in S_{\mathrm{COMP}}\setminus S_{\mathrm{DD}}\), we say that a test resolves \(i\) if it contains \(i\), exactly one element of \(S_{\mathrm{DD}}\), and no other element of \(S_{\mathrm{COMP}}\setminus S_{\mathrm{DD}}\). Such a test definitively classifies \(i\) from its outcome. Thus, to successfully recover the remaining defectives in \(S \setminus S_{\rm DD}\), it suffices to resolve the status of all items in \(S_{\rm COMP} \setminus S_{\rm DD}\). For a given test, the choice of test design implies that probability of exactly 1 item from \(S_{\rm DD}\) being included in a given test is \(\nu e^{-\nu}(1+o(1))\). Thus, the expected number of such tests is \(T_2 \, \nu e^{-\nu}(1+o(1))\). It can then be shown that the actual number of such tests is tightly concentrated around its mean with high probability due to McDiarmid’s inequality (Lemma 4).

Conditioned on this concentration event, and fixing an item \(i \in S_{\rm COMP} \setminus S_{\rm DD}\), it follows that each test drawn for \(i\) to be included in contains exactly one item from \(S_{\rm DD}\) with probability at least \(\nu e^{-\nu}(1-o(1))\). Thus, the probability that it is not resolved by a test in any of the \(L_2\) draws with replacement is at most \((1 - \nu e^{-\nu}(1-o(1)))^{L_2}\), which can be expressed as \(\exp\big(\frac{T_2 \nu}{k} \log(1 - \nu e^{-\nu})(1-o(1))\big)\). Following a union bound over at most \(k\) uncertain items, it follows that \(T_2 = \frac{k\log k}{\nu\,\log \frac{1}{1-\nu e^{-\nu}}}(1+o(1))\) tests suffice to ensure every \(i \in S_{\rm COMP} \setminus S_{\rm DD}\) is resolved with high probability. Numerically optimizing \(\nu\) gives a denominator of roughly \(0.636\), improving on \((\ln 2)^2\approx 0.48\) (e.g., appearing in the analysis of DD for standard GT in [18]). Summing the contribution from batch 1 and batch 2, we obtain the following (see Theorem 4 for a general and formal version): \[T \approx \frac{1}{\log2} k\log_2(n/k) + \frac{k\log k}{0.636}. \label{eq:T95NCC95gamma2}\tag{4}\] Writing \(\log k=\frac{\theta \log 2}{1-\theta}\log_2\frac{n}{k}\), the normalized rate becomes roughly \(\big(\frac{1}{\log 2} +\frac{\theta\log 2}{0.636(1-\theta)}\big)^{-1}\). Note that the second term dominates for \(\theta\) close to one, which will be important when comparing to the converse in Section 3.

2.3.2 Extension to general \(\gamma_{\max} = r\)↩︎

For the general case, we adopt the same two-batch approach, alongside the same test designs. Batch 1 proceeds in exactly the same manner as before, with the only changes arising in the second batch.

In the second batch, each item \(i \in S_{\rm COMP} \setminus S_{\rm DD}\) is now resolved in a test if it contains exactly \(r-1\) items from \(S_{\rm DD}\), and \(i\) is the only item included from \(S_{\rm COMP} \setminus S_{\rm DD}\). The probability that a test contains exactly \(r-1\) items from \(S_{\mathrm{DD}}\) can be determined via a Poisson approximation to the binomial (along with \(|S_{\rm DD}| = k(1-o(1))\)): \[\label{eq:S95DD95poisson} \Pr\left({\rm Bin}\left(\lvert S_{\rm DD}\rvert, \frac{\nu}{k}(1+o(1))\right) = r-1\right) = \frac{\nu^{r-1}e^{-\nu}}{(r-1)!}(1+o(1)).\tag{5}\] As in the previous case, the number of tests that contain exactly \(r-1\) items from \(S_{\rm DD}\) is tightly concentrated around its mean \(T_2 \,\nu^{r-1}e^{-\nu}/(r-1)!\) with high probability due to McDiarmid’s inequality. Conditioned on this, each uncertain item has \(L_2=\frac{T_2 \nu}{k}\) placements that each “succeed” with probability \(\nu^{r-1}e^{-\nu}/(r-1)! \cdot (1+o(1))\), meaning the “overall failure” probability is given by \(\exp\big(\tfrac{T_2\nu}{k}\log(1-\nu^{r-1}e^{-\nu}/(r-1)!)(1-o(1))\big)\). A union bound then implies that \[T_2 = \frac{k\log k}{\nu\,\log\Big(\frac{1}{1-\nu^{r-1}e^{-\nu}/(r-1)!}\Big)}(1+o(1))\] tests suffice for all uncertain items to be resolved with high probability. The above findings are summarized as follows.

The detailed proof of this result can be found in Appendix 6.3.

3 Converse Results↩︎

3.1 Useful Definitions↩︎

We introduce some useful notation in addition to that of Section 1.1. For each test \(t \in [T]\), we let \(w_t+1\) denote its weight,³ i.e., the number of items included in test \(t\), and for each item \(i \in [n]\), we denote by \(d_i\) its degree, i.e., the number of tests in which item \(i\) participates. We let \(\Gamma\) denote the set of thresholds that the algorithm is allowed to choose; in Section 1.1 we adopted \(\Gamma = \{1,2,\dotsc,\gamma_{\max}\}\), but we will consider the more general case of an arbitrary set of thresholds: \[\Gamma = \{\gamma_1, \dots, \gamma_\ell\}, \label{eq:Gamma}\tag{6}\] where \(\ell\) is the number of unique thresholds. We do this because this generalization comes “for free”.

As with converse bounds for standard group testing [19], [32], we will consider two prior models for the defective set \(S \subset [n]\):

• All of our main results will be stated for the combinatorial prior in which \(S\) is uniform on the \(n \choose k\) subsets of \([n]\) of size \(k\), as we assumed in Section 1.1.

• As a stepping stone in the analysis, we will also consider the i.i.d. prior, in which each item is independently defective with some probability \(q\).

Lastly, we introduce a notion of items being masked (or disguised) that generalizes such notions from standard GT [20], [32], [33]. Let \(i \in [n]\) and let \(t \in [T]\) be a test with threshold \(\gamma^{(t)}\). We say that the test \(t\) is informative for item \(i\) if \(i\) participates in \(t\) and, among the remaining items in the test (excluding \(i\)), there are exactly \(\gamma^{(t)} - 1\) defectives. This is significant because it means that the outcome of test \(t\) changes when \(i\) is changed from defective to non-defective or vice versa. An item \(i\) is said to be masked if there are no tests that are informative for \(i\). This is a random event due to the randomness in \(S\), and we let \(D_i\) denote the event that \(i\) is masked (or \(i\) is disguised, hence the symbol \(D\)).

3.2 The Single-Threshold Setting↩︎

We begin with the simple setting in which the threshold set contains only a single value, i.e., \(\Gamma = \{\gamma\}\). This recovers the TGT problem, and it captures most of the ideas for the GT-ST problem while simplifying notation and proofs.

3.2.1 Discussion: Failure of Standard GT Techniques↩︎

It is tempting to seek a converse via the same techniques as standard GT [20], but (selectable) threshold group testing faces major technical barriers when doing so, which we now proceed to outline.

If we momentarily consider an i.i.d. defectivity prior in which each item is defective independently with some probability \(q\) (as is done in [20]), then a simple calculation reveals that for a given test \(t\) containing \(i\), the probability of the test being uninformative for \(i\) is \(\Phi_{t,i} \mathrel{\vcenter{:}}= 1 - \Pr(\mathrm{Bin}(w_t,q)=\gamma-1)\), where \(w_t = \sum_{j : j \ne i} x_{tj}\) is the number of items in test \(t\) excluding \(i\). Moreover, the binomial probability can readily be characterized tightly using a Poisson approximation (when \(q = o(1)\) and \(\gamma\) is fixed).

However, the major technical obstacle is that we cannot directly conclude that \(\Pr(D_i) \ge \prod_{t : x_{ti} = 1} \Phi_{t,i}\). When \(\gamma = 1\), such a claim follows from the FKG inequality and the fact that the “uninformative” events are increasing – changing any item from non-defective to defective can only expand (or keep unchanged) the set of tests that are uninformative for \(i\). For threshold GT with \(\gamma \ge 2\), this is no longer the case; for instance, a given test may have contained item \(i\) and a total of \(\gamma - 2\) other defectives, and changing a non-defective to defective could increase that to \(\gamma - 1\), thus changing the test from uninformative to informative.

Our results turn out to match what would have been obtained if the FKG inequality were to remain valid, but we do so via a distinct approach that separates the tests whose number of defectives is “at most \(\gamma - 2\)” vs. “at least \(\gamma\)”. In order to control the dependencies between the relevant events, we turn out (at least for our proof) to require some additional assumptions, but we argue that these are reasonable, and show that they are indeed satisfied by the NCC random design.

3.2.2 Assumptions↩︎

The regularity assumptions that we adopt are formally stated as follows.

Assumption 1 states that all items have the same degree to within a \(1+o(1)\) factor, and all tests have the same weight to within a \(1+o(1)\) factor. The assumption \(T = \Theta(k \log n)\) is without loss of generality for proving a converse, since the counting bound prevents any smaller scaling (when \(k = \Theta(n^{\theta})\)), and all of our achievability results match this scaling. Given the near-constant weight condition, the assumption of row weight \(\Theta(n/k)\) is also easily justified, because any other scaling would yield \(o(1)\) entropy per test, thus requiring \(T = \omega(k \log n)\) via Fano’s inequality (e.g., see [34]). Moreover, given a near-constant row weight of \(\Theta(n/k)\) and \(T = \Theta(k \log n)\), a simple double counting argument reveals that the column weight must be \(\Theta(\log n)\).

The interpretation of Assumption 2 is less immediately obvious. It ensures that the tests do not overlap too much, so that the information contributed by two different tests remains largely “independent”. (Specifically, the fraction of overlap is constrained to scale as \(o\big( \frac{1}{\log n} \big)\).) Intuitively, this would be a preferable property to have anyway, but dropping it as a formal assumption here still appears to be challenging.

In Appendix 8, we show that the NCC design (Definition 2) with \(\nu = \Theta(1)\) and \(T = \Theta(k \log n)\) satisfies both assumptions with probability \(1-o(1)\). Moreover, the analysis shows that the above \(o(1)\) terms come out to be much smaller than required (e.g., polynomially small in \(n\)), meaning that the assumptions hold with a “significant margin” for this design.

For the Bernoulli design (Definition 1), the degrees \(d_i\) turn out to fail to be near-constant, since they do not concentrate sharply enough. While this is actually the cause of the design being weaker than NCC design (e.g., see the discussion in [15]), this observation may still limit “how mild” Assumption 1 can be considered to be. While our analysis can be adapted to handle \(\zeta > 1\), the resulting lower bound on \(T\) becomes worse as \(\zeta\) increases.

3.2.3 Statement of Converse Result↩︎

We are now ready to state our converse result for the single-threshold setting, which we prove in Appendix 7.2.

3.2.4 Discussion↩︎

Theorem 5 matches the “non-entropy term” for the exact threshold of the near-constant column weight design established in concurrent work [30]. As discussed in the introduction, our converse holds in greater generality, since it is not restricted to the random design of Definition 2, but instead holds for general deterministic designs satisfying Assumptions 1 and 2. Under these assumptions, the entropy term from [30] can also readily be established via Fano’s inequality (e.g., similar to [34]), at least when considering the requirement \(\Pr(\hat{S} \ne S) \nrightarrow 0\) rather than \(\Pr(\hat{S} \ne S) \to 1\) (i.e., a “weak converse” rather than a “strong converse”). We omit the details, since it was observed in [30] that the tighter of the counting bound and Theorem 5 is correct for all \(\theta\) except a very narrow “transition region”. For instance, when \(\gamma = 2\), this region occurs at \(\theta \approx 0.4785\) and has a width of less than \(0.005\); see [30]. (The transition region for \(\gamma = 10\) therein is also imperceptible in a zoomed out plot.)

3.3 The Selectable-Threshold Setting↩︎

We now turn to the general setting in which tests may have different thresholds, i.e., \(\Gamma = \{\gamma_1, \dots, \gamma_\ell\}\), where \(\ell\) is the number of distinct thresholds. The near-constant row weight part of Assumption 1 may be overly restrictive in this setting, since it may be highly suboptimal to keep the same row weight across different thresholds. Accordingly, we adopt a natural generalization (stated below) allowing each threshold to have a different weight (but still near-constant among all tests using that threshold).

3.3.1 Assumptions↩︎

We keep Assumption 2 unchanged, but generalize Assumption 1 to the following.

In short, this means that up to re-ordering tests, \(\mathbf{X}\) is the vertical concatenation of \(\ell\) matrices satisfying Assumption 1, each with a different threshold \(\gamma_r\) and possibly different degrees and weights. While not every sequence of tests designs necessarily consists of \(\Theta(k \log n)\) tests for every threshold, assuming this is convenient and very mild; intuitively, for the purpose of proving a converse, each threshold could be given \(\epsilon k \log n\) additional tests “for free”, with an arbitrarily small impact on the rate as \(\epsilon\) decreases (since \(\ell\) is constant).

3.3.2 Statement of Converse Results↩︎

Given that the test design satisfies Assumptions 2 and 3 above, we proceed to state our main converse bound for the GT-ST problem. We initially suppose that the fraction of tests with threshold \(\gamma_r\) is some fixed quantity \(\alpha_r \in (0,1)\) (i.e., \(\lvert \mathcal{T}_r\rvert = \alpha_r T\)), for each \(r \in [\ell]\), and then provide a corollary in which we optimize over \(\alpha_r\). The main theorem is proved in Appendix 7.3, and the subsequent two lemmas are proved in Appendices 7.4 and 7.5.

We now consider the optimization over the threshold proportions \((\alpha_1, \dots, \alpha_\ell)\) and the threshold-dependent weight parameters \((\Delta_1,\dotsc,\Delta_r)\), both of which may be chosen to minimize the number of tests. This optimization leads to the bound in Theorem 5 with \(\gamma = \gamma_{\max}\), as we will discuss further below. Note that while Theorem 6 assumes \(\alpha_r > 0\) for all \(r\), we may safely include \(\alpha_r \in \{0,1\}\) in the optimization since this simply amounts to removing one or more thresholds, i.e., shrinking the set \(\Gamma\) in 6 (Theorem 6 holds for any such set).

Lastly, we investigate the asymptotic behavior of \(\max_{\Delta > 0} h(\Delta,\gamma)\) in the large-threshold limit \(\gamma \to \infty\), as characterized in the following lemma.

Combining these lemmas, we find that the maximum value of \(f(\boldsymbol{\alpha},\boldsymbol{\Delta},\boldsymbol{\gamma}) =\sum_{r\in[\ell]}\alpha_r h(\Delta_r,\gamma_r)\) also satisfies \[\max_{\boldsymbol{\alpha},\boldsymbol{\Delta}} f(\boldsymbol{\alpha},\boldsymbol{\Delta},\boldsymbol{\gamma}) \sim \sqrt{\frac{\gamma_{r^*}}{2\pi}} \qquad \text{as } \gamma_{r^*}\to\infty,\] where \(r^*=\arg\max_{r\in[\ell]}\gamma_r\) and thus \(\gamma_{r^*} = \gamma_{\max}\). Combined with the counting bound from Theorem 1 and the fact that \(k \log k = \frac{\theta\log 2}{1-\theta} k\log_2\frac{n}{k}\), this gives the following corollary.

3.3.3 Discussion↩︎

Lemma 1 reveals that the largest denominator in 8 is obtained when all of the tests use a threshold of \(\gamma_{\max}\), thus simplifying Theorem 6 to the single-threshold result of Theorem 5. This suggests that the flexibility of selectable thresholds may have limited (if any) benefit when it comes to the information-theoretic limits. However, as we saw in Section 2, the notion of selectable thresholds can lead to distinct algorithmic ideas and the ability to incorporate methods from the standard GT setting.

We observe that Theorem 5 (with \(\gamma_{\max}\)) exactly matches the second term in Theorem 4. When \(\theta\) is very close to 1, the remaining \(O\big(k \log\frac{n}{k} \big)\) becomes insignificant, so when expressing the results as a coefficient to \(k \log k\) (rather than the usual \(k \log \frac{n}{k}\)), we find that the achievability and converse bounds match as \(\theta \to 1\). However, for fixed \(\theta \in (0,1)\) a gap remains, as seen in Figure 1.

Finally, one interpretation of Corollary 1 is that the number of tests must always have a \(k \log k\) term whose coefficient decays no faster than \(\Theta\big(\frac{1}{\sqrt{\gamma_{\max}}}\big)\). This implies that in our achievable number of tests in 3 , the \(\frac{1}{\sqrt{\gamma_{\max}}}\) dependence in the second term cannot be improved. (While it uses \(k \log n\) instead of \(k \log k\), the two are equivalent to within a constant factor except when \(\theta \to 0\), and they are equivalent to within \(1+o(1)\) as \(\theta \to 1\).) However, this does not rule out the possibility of improving 3 in other ways; in particular, the sum would ideally be replaced by a maximum, and the precise hidden constant in \(O(\cdot)\) could be sought.

4 Conclusion↩︎

We have introduced the problem of Group Testing with Selectable Thresholds (GT-ST), and established several achievability and converse bounds summarized as follows depending on the maximum threshold \(\gamma_{\max}\):

• For unbounded \(\gamma_{\max}\), the optimal rate is 1.

• For large \(\gamma_{\max}\), a rate of the form \(1 - O\big(\frac{1}{\sqrt{\gamma_{\max}}}\big)\) can be achieved, and under the regularity conditions in our converse, the coefficient to \(k \log k\) cannot decay any faster than \(\frac{1}{\sqrt{\gamma_{\max}}}\).

• For fixed \(\gamma_{\max}\), our achievability and converse results coincide in the limit \(\theta \to 1\), but there is a gap between the two for fixed \(\theta \in (0,1)\).

Some immediate directions for future research include the following:

• Other algorithmic benefits of selectable thresholds. We have seen that allowing selectable thresholds does not improve the optimal rate compared to only allowing the highest threshold. However, it could still be of interest to further explore the extent to which the added flexibility can simplify algorithm design, possibly using more than two thresholds (unlike our approach that only uses the smallest and largest thresholds).

• Converse for arbitrary designs. We expect that our main converse results should hold for arbitrary test designs, but formally proving this appears to be difficult.

5 Technical Lemmas↩︎

Here we present some useful technical lemmas that are used throughout the paper.

To state the next lemma, we require the following definition:

6 Achievability Proofs↩︎

6.1 Proof of Theorem 2 (Achievability for Unbounded \(\gamma_{\max})\)↩︎

As discussed in Section 2, our algorithm consists of two batches of tests: the first batch uses \(T_1 = (k \log_2 \frac{n}{k})(1+o(1))\) tests to run the Subset algorithm from [22], which yields an estimate \(\widehat{S}_1 \subseteq S\) of size \(\lvert \widehat{S}_1 \rvert \geq k - k /\log^4k\) with probability \(1-o(1)\). Throughout the rest of the proof, we will implicitly condition on this first batch being successful. In the second batch, we aim to resolve the status of the remaining \(\lvert S \setminus \widehat{S}_1 \rvert \leq k/\log^4k\) tests by doing the following:

1. Design \(T_2'= (\frac{ek}{\log^4k} \log n)(1+o(1))\) tests for a standard group testing problem with \(k/\log^4 k\) defectives by using a Bernoulli design (Definition 1) with inclusion probability \(p = \frac{\log^4k}{k}\).

2. Repeat each of the \(T_2'\) tests \(R\) times (for a total of \(T_2 = R \cdot T_2'\) tests) for some \(R > 0\) to be determined later. In the \(r\)-th repetition of each test, the chosen defectivity threshold is \(\gamma_r = \tau + r-1\) for some \(\tau > 0\) also to be determined later.

3. For each test \(t \in [T_2']\), do the following: (i) if all of its repetitions return the same outcome, then declare \(\psi_t\) as undetermined and declare an error; (ii) otherwise, identify \(\psi_t\) as the highest threshold \(\gamma_r\) for which the test outcome is 1.

4. For each test \(t \in [T_2']\), subtract the number of items from \(\widehat{S}_1\) in the test from \(\psi_t\). Convert this to a standard group testing observation by setting \(Y_t = 1\) if the residual number of defectives is non-zero (otherwise \(Y_t = 0\)).

5. Using the test design for the \(T_2'\) tests and the standard group testing outcomes \(Y_1,\dots, Y_{T_2'}\), run the COMP algorithm to recover the remaining \(\lvert S \setminus \widehat{S}_1 \rvert \leq k/\log^4k\) defectives.

Suppose that we can show (with high probability) that:

• There exist values of \(R,\tau\) such that all values of \(\psi_t\) lie within the set \(\{\tau + 1, \tau + 2,\dots, \tau + R-2\}\), and \(T_2 = R\cdot T_2' = o(k \log n)\);

• \(T_2'\) tests suffice to recover the remaining \(\lvert S \setminus \widehat{S}_1 \rvert \leq k/\log^4k\) defectives from the standard GT outcomes.

Then, a rate of \(1\) is achievable in the GT-ST problem with unbounded \(\gamma_{\max}\), since all defectives are recovered, and the number of tests across both stages is \[\label{eq:unbounded95both95stages95tests} T = \Big(k \log_2 \frac{n}{k}\Big)(1+o(1)) + o(k \log n) = \Big(k \log_2 \frac{n}{k}\Big)(1+o(1)).\tag{9}\] We now proceed to show each of these statements hold:

Establishing Statement (i). To find appropriate values of \(R,\tau\), observe that if \(\psi_t\) is known to lie (with high probability) in an interval \((a,b)\) for all \(t\), the choices \(\tau = \lfloor a \rfloor , \; R = \lceil b\rceil - \lfloor a \rfloor +1\) suffice to ensure that \(\psi_t \in \{\tau + 1, \tau +2,\dots, \tau + R-2\}\), since \(\tau \leq a\) and \(\tau + R-1 \geq b\). Therefore, determining \(R,\tau\) reduces to proving the existence of such an interval of size \(o(\log^4 k)\), which can be shown via a concentration argument. Specifically, we wish to show that the deviation of \(\psi_t\) from its mean is \(o(\log^4k)\) for all \(t\) with high probability, which will give us the desired interval. Since the tests follow a Bernoulli design with parameter \(p = \frac{\log^4k}{k}\), the total number of defectives \(\psi_t\) in a test is a \({\rm Bin}(k, p)\) random variable with mean \(\mu_\psi \mathrel{\vcenter{:}}= \mathbb{E}[\psi_t] = \log^4 k\). Thus, the multiplicative Chernoff bound (Lemma 3) and a union bound over all \(T_2'\) tests imply that \[\label{eq:pos95test95conc} \Pr(\exists t \in \{1,\dots, T_2'\} :\lvert \psi_t - \mu_\psi \rvert \geq \delta \mu_\psi) \leq 2T_2' \exp\Big(-\frac{\delta^2\mu_\psi}{3}\Big)\tag{10}\] for any \(\delta \in (0,1)\). We then choose \(\delta = \sqrt{\frac{3}{\mu_\psi}\log (2kT_2')}\), which ensures that \[\label{eq:unbounded95conc95interval} \psi_t \in \big((1-\delta)\mu_\psi, (1+\delta)\mu_\psi\big), \;\forall t \in \{1,\dots, T_2'\}\tag{11}\] with probability \(1 - o(1)\). In accordance with our previous discussion, we can then set \[\label{eq:choice95R95phi} \tau = \lfloor (1-\delta)\mu_\psi\rfloor , \quad R = \lceil (1+\delta)\mu_\psi\rceil - \lfloor (1-\delta)\mu_\psi\rfloor + 1 = O(\delta\mu_\psi)\tag{12}\] to ensure that \(\psi_t \in \{\tau + 1,\tau + 2, \dots, \tau + R - 2\}\) for all \(t\) with probability \(1-o(1)\). Finally, to obtain a bound on the scaling of \(R\), we observe from the choice of \(\delta\) that \[\begin{align} \tag{13} \delta\mu_\psi &= \sqrt{3\mu_\psi \log (2kT_2')} \\ \tag{14} &= \log^2k \sqrt{3 \log(2kT_2')} \\ \tag{15} &= O(\log^{5/2} k), \end{align}\] where 15 uses the fact that \(T_2' = O(k\log n/\log^4 k)\). Hence, \(R = O(\log^{5/2}k)\), implying that the number of tests required to learn the thresholds \(\psi_t\) is \[\label{eq:T2} T_2 = R \cdot T_2' = O(\log^{5/2} k ) \times O\left(\frac{k}{\log^4 k}\log n\right) = o(k \log n),\tag{16}\] as desired. This implies that statement (i) holds with probability \(1-o(1)\).

Establishing Statement (ii). Conditioned on statement (i) holding, we now show that \(T_2' = (\frac{ek}{\log^4k}\log n)(1+o(1))\) tests suffice to recover the remaining \(\lvert S \setminus \widehat{S}_1 \rvert \leq k/\log^4k\) defectives using the COMP algorithm. While this claim follows directly from standard results for COMP [39], we formally prove it here for completeness, and since the argument is relatively simple.

Recall that the COMP algorithm fails if there is at least one non-defective item that does not appear in any negative tests. Further recalling that the tests follow a Bernoulli design, the probability of a non-defective item appearing in a given test, alongside the test being negative is \(p(1-p)^{\lvert S \setminus \widehat{S}_1\rvert}\). Therefore, the probability that any given non-defective appears in no negative tests is \((1 - p(1-p)^{\lvert S \setminus \widehat{S}_1\rvert})^{T_2'}\). Using the fact that \(\lvert S \setminus \widehat{S}_1 \rvert \leq k/\log^4k\) and recalling that \(p = \frac{\log^4k}{k}\), this probability can be upper bounded by \((1-p(1-p)^{1/p})^{T_2'}\), which we can further upper bound by \(\exp(-T_2' \, p(1-p)^{1/p})\). A union bound over all non-defective items then implies that \[\label{eq:comp95error} \Pr \left( \bigcup_{i \in [n] \setminus S} \{i \text{ is not in any negative tests} \}\right) \leq n\exp\left(-T_2' \,p(1-p)^{1/p}\right),\tag{17}\] where we have upper bounded the number of non-defectives by \(n\). Choosing \[\label{eq:T9523995choice} T_2' = \frac{\log n}{p(1-p)^{1/p}}\Big(1 + \frac{1}{\log \log n}\Big)\tag{18}\] ensures that the error probability is upper bounded by \(n^{-1/\log \log n} = o(1)\). Finally, applying \((1-p)^{1/p} = e^{-1}(1-o(1))\) and substituting in the value of \(p\) implies that the number of tests sufficient for COMP to succeed with probability \(1-o(1)\) is \(T_2' = (\frac{ek}{\log^4k} \log n)(1+o(1))\), which implies that statement (ii) holds with probability \(1-o(1)\).

The proof of Theorem 2 is completed by combining 9 with the fact that both statements (i) and (ii) hold with probability \(1-o(1)\).

6.2 Proof of Theorem 3 (Achievability for Large \(\gamma_{\max}\))↩︎

In the case that \(\gamma_{\max}\) is “bounded but large”, we use a similar two-batch template to the one used in the proof of Theorem 2. The first batch proceeds in the exact same way as in Theorem 2, so we do not repeat the details. For the second batch (conditioned on batch 1 succeeding), we do the following:

1. Design \(T_2' = (\frac{8k}{\gamma_{\max}}\log n)(1+o(1))\) tests using a Bernoulli design with inclusion probability \(p = \frac{\gamma_{\max}}{2k}\), and calculate \(\psi_{t,1}\), the number of Subset-identified defectives in test \(t\) for each \(t \in [T_2']\).

2. Define the interval \((\gamma^-, \gamma^+) \mathrel{\vcenter{:}}= (\frac{\gamma_{\max}}{2} - 2\sqrt{\gamma_{\max}}, \,\frac{\gamma_{\max}}{2} + 2\sqrt{\gamma_{\max}})\), and repeat each of the \(T_2'\) tests with incrementing thresholds \(\lfloor \gamma^-\rfloor, \lfloor\gamma^-\rfloor + 1, \dots, \lceil \gamma^+ \rceil\), for a total of \(T_2 = \gamma_{{\rm dif}}\cdot T_2'\) tests, where we define \(\gamma_{{\rm dif}} \mathrel{\vcenter{:}}= \lceil \gamma^+\rceil - \lfloor\gamma^-\rfloor + 1\).

3. For each test \(t \in [T_2']\), observe the test outcomes \(\{Y_{t,r}\}_{r=0}^{\gamma_{{\rm dif}}-1}\), with the \(r\)-th test outcome being given by \(Y_{t,r} =\mathbb{1} \{\psi_t \geq \lfloor \gamma^-\rfloor + r\}\), and discard those whose test outcomes \(\{Y_{t,r}\}_{r=0}^{\gamma_{\rm dif}-1}\) are all identical (as this implies these tests’ values of \(\psi_t\) lie outside of \((\gamma^-, \gamma^+)\)).

4. For the remaining \(\widetilde{T}_2 \leq T_2'\) tests, use the test outcomes \(\{Y_{t,r}\}_{r=0}^{\gamma_{\rm dif} -1 }\) to find \(\psi_t\), and calculate the number of non Subset-identified defectives \(\widetilde{\psi}_t = \psi_t - \psi_{t,1}\) in the test.

5. Defining a test \(t \in[\widetilde{T}_2]\) to be residually negative if \(\widetilde{\psi}_t = 0\), return the subset of items from \([n] \setminus \widehat{S}_1\) that do not appear in any residually negative tests (i.e., declare them to be defective).

To prove Theorem 3, it suffices to show that out of the non-discarded \(\widetilde{T}_2\) tests, there are sufficiently many residually negative tests, so that all non-defectives are included in at least one with high probability. To this end, we first derive a (high probability) lower bound on \(\widetilde{T}_2\).

In any given test \(t \in [T_2']\), each item is included in it independently with probability \(p = \frac{\gamma_{\max}}{2k}\). Thus, \(\psi_t\) has a \({\rm Bin}(k, p)\) distribution with mean \(\mu_\psi \mathrel{\vcenter{:}}= \mathbb{E}[\psi_t] =\frac{\gamma_{\max}}{2}\). The multiplicative Chernoff bound (Lemma 3) thus implies that \[\label{eq:ell95t95conc} \Pr(\lvert \psi_t - \mu_\psi \rvert \geq 2\sqrt{\gamma_{\max}}) \leq 2 \exp\left(-\frac{8}{3}\right) \approx 0.139.\tag{19}\] Thus, the number of defectives \(\psi_t\) lies within \((\gamma^-, \gamma^+)\) with probability at least \(1 - 2\exp(-8/3) \approx 0.861\). Since the number of defectives is independent across tests, it follows that the number of non-discarded tests \(\widetilde{T}_2\) stochastically dominates a \({\rm Bin}(T_2', 1 - 2\exp(-8/3))\) random variable. Using this and the multiplicative Chernoff bound, it follows that \[\label{eq:T295tilde95conc} \Pr\left(\widetilde{T}_2 \leq \frac{1}{2}T_2'\right) \leq \Pr\left({\rm Bin}(T_2', 1 - 2\exp(-8/3)) \leq \frac{1}{2}T_2'\right) = o(1).\tag{20}\] Thus, \(\widetilde{T}_2 \geq \frac{1}{2}T_2'\) with probability \(1-o(1)\).

We now show that a constant fraction of the non-discarded tests are residually negative, i.e., contain no item from \(S \setminus \widehat{S}_1\). To do so, we momentarily return to considering the entire sequence of tests indexed by \(t \in [T'_2]\), and let \(B\) denote the number of such tests containing at least one item from \(S \setminus \widehat{S}_1\). Using \(\lvert S \setminus \widehat{S}_1 \rvert \leq k/\log^4k\) and Bernoulli’s inequality, a given test contains an item from \(S \setminus \widehat{S}_1\) with probability at most \[\label{eq:residual95negative95lb} 1 - \left(1 - \frac{\gamma_{\max}}{2k}\right)^{k/\log^4k} \leq \frac{\gamma_{\max}}{2\log^4k}.\tag{21}\] Since the tests are independent, this implies that \(B \preceq_{\rm st}{\rm Bin}(\widetilde{T}_2, \frac{\gamma_{\max}}{2\log^4 k})\). Thus, the Chernoff bound and the fact that \(\frac{\gamma_{\max}}{2\log^4 k} = o(1)\) imply that \(B \le \frac{1}{4}T_2'\) with probability \(1-o(1)\). Combined with the previous paragraph, this implies that the number of non-discarded residually negative tests is at least \(\widetilde{T}_2 - \frac{1}{4}T_2' \geq \frac{1}{4}T_2'\) with probability \(1-o(1)\).

Fix a non-defective item \(i \in [n] \setminus S\). Conditioned on there being at least \(\frac{1}{4}T_2'\) residually negative tests, the probability that \(i\) appears in none of them (thus being incorrectly classified as defective) is upper bounded by \((1 - \frac{\gamma_{\max}}{2k})^{T_2'/4}\), which can be further upper bounded by \(\exp(-\frac{T_2'\gamma_{\max}}{8k})\). Taking a union bound over all non-defective items (of which there are at most \(n\)), the probability of any non-defective not appearing in any residually negative test is upper bounded by \(n\exp(- \frac{T_2'\gamma_{\max}}{8k})\). The choice \(T_2' = (\frac{8k}{\gamma_{\max}}\log n)(1+\frac{1}{\log \log n})\) therefore implies that this probability is upper bounded by \(n^{-1/\log \log n} = o(1)\). Since each of the designed \(T_2'\) tests is conducted a total of \(\gamma_{\rm dif} \mathrel{\vcenter{:}}= \lceil \gamma^+ \rceil - \lfloor \gamma^- \rfloor + 1 = O(\sqrt{\gamma_{\max}})\) times, the total number of tests conducted is \[\begin{align} \tag{22} T_2 &= \gamma_{\rm dif} \cdot T_2' \\ \tag{23} &= O(\sqrt{\gamma_{\max}}) \times \left(\frac{8k}{\gamma_{\max}}\log n \right)\left(1 + \frac{1}{\log \log n}\right) \\ \tag{24} &= O\left(\frac{k}{\sqrt{\gamma_{\max}}}\log \frac{n}{k}\right), \end{align}\] where 24 follows since \(\log n = \Theta(\log \frac{n}{k})\), as \(k = \Theta(n^\theta)\) for some \(\theta \in (0,1)\). We conclude by noting that the number of tests across both batches is \[\label{eq:large95T95total} T = \Big(k \log_2 \frac{n}{k}\Big)(1+o(1)) + O\left(\frac{k}{\sqrt{\gamma_{\max}}}\log \frac{n}{k}\right),\tag{25}\] thus completing the proof.

6.3 Proof of Theorem 4 (Achievability for Fixed \(\gamma_{\max}\))↩︎

In the case that \(\gamma_{\max} = r\) for some fixed \(r > 0\), we again adopt a two-batch approach. In the first batch, we apply a standard group testing algorithm with \(T_1\) tests, similarly to the approaches taken in Theorems 2 and 3. Unlike these approaches, however, we incorporate a different test design and decoder, which we now outline:

• Rather than designing tests using a Bernoulli design (Definition 1) with inclusion probability \(p = \frac{\log 2}{k}\), the tests in batch 1 are now designed according to a near-constant column weight (NCC) design (Definition 2), with each item being independently placed in \(L_1 = \frac{T_1 \log 2}{k}\) tests chosen uniformly at random with replacement.

• Rather than using \((k \log_2 \frac{n}{k})(1+o(1))\) tests in the first batch, we now let this number be \(T_1 = (\frac{k}{\log 2}\log_2 \frac{n}{k})(1+o(1))\).

• Rather than using the Subset algorithm from [22] as our decoder, we apply both COMP and DD decoders (Section 1.2) to the test outcomes, and rely on their approximate recovery guarantees.

The reason for switching to the NCC design is that it has strictly better constants than the Bernoulli design when paired with COMP or DD decoding. Moreover, the reason for switching to COMP and DD is (i) these are very simple and computationally efficient, and (ii) the SUBSET and SUPERSET problems are handled separately in [22], whereas the use of COMP and DD provides a simple way to obtain a subset and a superset simultaneously.

It is well known (see e.g., [15]) that both COMP and DD can be run in polynomial time. Additionally, the analysis in [22] reveals that under our choice of \(T_1\), the COMP and DD algorithms produce sets \(S_{\rm COMP} \supseteq S\) and \(S_{\rm DD} \subseteq S\) of size \(k(1+o(1))\) and \(k(1-o(1))\) respectively, with probability \(1-o(1)\).

Conditioned on batch 1 “succeeding” (i.e., the sets \(S_{\rm COMP}\) and \(S_{\rm DD}\) satisfying the above properties), we then do the following in batch 2:

1. Design \[\label{eq:fixed95T952} T_2 = \frac{k \log k}{\nu \log\Big(\frac{1}{1 - \nu^{r-1}e^{-\nu}/(r-1)!}\Big)}(1+o(1))\tag{26}\] tests according to the NCC design with parameter \(L_2 = \frac{T_2 \nu}{k}\), where \(\nu >0\) will be optimized later.

2. Conduct each of the \(T_2\) tests with defectivity threshold \(\gamma = \gamma_{\max} = r\).

3. For each \(i \in S_{\rm COMP} \setminus S_{\rm DD}\), find a test \(t \in [T_2]\) such that (i) there are exactly \(r-1\) items from \(S_{\rm DD}\) included in the test, and (ii) the only item from \(S_{\rm COMP} \setminus S_{\rm DD}\) included in the test is \(i\). If there exists some \(i \in S_{\rm COMP} \setminus S_{\rm DD}\) having no such tests, then declare an error.

4. Classify each \(i \in S_{\rm COMP} \setminus S_{\rm DD}\) as defective if \(Y_{t_i} = 1\), and non-defective otherwise, where \(t_i \in [T_2]\) is a test satisfying conditions (i) and (ii) above for \(i\).

5. Declare the defective set as the union of \(S_{\rm DD}\) and the set of classified defectives from \(S_{\rm COMP} \setminus S_{\rm DD}\).

It is straightforward to verify that this procedure runs in polynomial time, e.g., by first forming a length-\(L_2\) list of which tests (of batch 2) each item is included in, one can readily verify \(O(nk \log n)\) runtime.

If a test \(t\) satisfies properties (i) and (ii) in step 3 above for an item \(i \in S_{\rm COMP} \setminus S_{\rm DD}\), we say that test \(t\) resolves item \(i\), since the status of \(i\) can be determined from the test outcome. Therefore, if there is at least one test that resolves \(i\) for all \(i \in S_{\rm COMP} \setminus S_{\rm DD}\), successful recovery is possible, since all items in \(S_{\rm COMP} \supseteq S\) can be correctly classified (meaning \(S\) can be correctly recovered). Thus, to show that \(S\) is successfully recovered (with high probability), it suffices to show that the choice of \(T_2\) leads to all \(i \in S_{\rm COMP} \setminus S_{\rm DD}\) being resolved by at least one test.

To do so, we first consider the probability that exactly \(r-1\) items from \(S_{\rm DD}\) are included in a test. The NCC design implies that each item is included in a test with probability \(1 -(1 - \frac{1}{T_2})^{L_2}\). Using the definition of \(L_2\), and the fact that \(\frac{\nu}{k} = o(1)\), this probability can be expressed as \[\begin{align} \tag{27} \Pr({\rm item} \;i \;{\rm in \;test } \;t) &= 1 - \left(1 - \frac{1}{T_2}\right)^{L_2} \\ \tag{28} &= 1 - \exp\left(- \frac{\nu}{k}\right)(1-o(1)) \\ \tag{29} &= \frac{\nu}{k}(1+o(1)). \end{align}\] Denote the number of items from \(S_{\rm DD}\) in test \(t\) by \(D_t\). The above calculations, and the fact that items are placed in tests independently of one another, imply that \(D_t \sim {\rm Bin}\big(\lvert S_{\rm DD}\rvert, \frac{\nu}{k}(1+o(1)\big)\). Since \(\lvert S_{\rm DD}\rvert \cdot \frac{\nu}{k}(1+o(1)) \to \nu\), the Poisson approximation to the binomial (Lemma 5) implies that \[\label{eq:D95t95poisson95approx} q_{\nu, r} \mathrel{\vcenter{:}}= \Pr(D_t = r-1) = \frac{\nu^{r-1}e^{-\nu}}{(r-1)!}(1+o(1)).\tag{30}\] Thus, each test contains \(r-1\) defectives from \(S_{\rm DD}\) with probability approaching \(\nu^{r-1}e^{-\nu}/(r-1)!\). Now, let \[\label{eq:defn95V} V = \sum_{t=1}^{T_2} \mathbb{1}\{D_t = r-1\}\tag{31}\] be the number of tests that include exactly \(r-1\) items from \(S_{\rm DD}\). By 30 and the linearity of expectation, it follows that \(\mu_V \coloneq \mathbb{E}[V] = q_{\nu, r} T_2\). To obtain a high probability lower bound on \(V\), define \(Z_{\ell i} \in [T_2]\) as the \(\ell\)-th test drawn for item \(i \in S_{\rm DD}\) to be included in, and note that there exists a function \(f:\mathbb{R}^{L_2\cdot \lvert S_{\rm DD}\rvert} \to \mathbb{R}\) such that \(V = f(\{Z_{\ell i}\}_{(\ell , i) \in [L_2] \times S_{\rm DD}})\). Moreover, changing the value of any \(Z_{\ell i}\) can lead to the value of \(V\) changing by at most two, since in the worst case, it could be removed from a test containing exactly \(r-1\) defectives from \(S_{\rm DD}\) including \(i\) (leading to \(V\) decreasing by one), and be added to a different test containing exactly \(r-1\) defectives from \(S_{\rm DD}\) not including \(i\) (leading to \(V\) further decreasing by one). Thus, \(f\) satisfies the bounded differences property ?? with \(c_{\ell i} =2\) for all \((\ell, i ) \in [L_2] \times S_{\rm DD}\), meaning we can apply McDiarmid’s inequality (Lemma 4) to obtain \[\begin{align} \tag{32} \Pr \left( \lvert V - \mu_V \rvert \geq \delta \right) &\leq 2\exp\left(- \frac{\delta^2}{2L_2 \lvert S_{\rm DD}\rvert}\right) \\ \tag{33} &= 2\exp\left(- \frac{\delta^2}{2\nu T_2} (1+o(1))\right) \end{align}\] for any \(\delta > 0\), where we applied \(L_2 = \frac{\nu T_2}{k}\) and \(|S_{\rm DD}| = k(1-o(1))\) in 33 . Choosing \(\delta = q_{\nu, r} T_2/\log n\) gives \[\label{eq:V95conc95delta95choice} \Pr \left(\lvert V - \mu_V \rvert \geq \frac{q_{\nu, r} T_2}{\log n}\right) \leq 2 \exp\left(- \frac{q_{\nu, r}^2T_2}{2\nu\log^2 n} (1+o(1))\right) = o(1),\tag{34}\] since \(T_2 = \Omega(k)\). In particular, this implies that \[\begin{align} \label{eq:V95lb951} V &\geq q_{\nu, r}T_2\Big(1 - \frac{1}{\log n}\Big) \end{align}\tag{35}\] with probability \(1-o(1)\).

Now, fix an item \(i \in S_{\rm COMP} \setminus S_{\rm DD}\). Let \(U_i\) be the number of tests that include any \(j \in S_{\rm COMP} \setminus S_{\rm DD}\) with \(j \ne i\). Since each item is placed in (at most) \(L_2 = \Theta(\log n)\) tests, and since \(|S_{\rm COMP} \setminus S_{\rm DD}| = o(k)\), we have \(U_i = o(k \log n) = o(T_2)\) (with probability one). Hence, conditioned on 35 holding, each of the \(L_2\) tests drawn for \(i\) to be included in resolves it with probability at least \[\label{eq:prob95resolve95single95test} \frac{V - U_i}{T_2} = q_{\nu, r} - o(1).\tag{36}\] Thus, the probability \(i\) is not resolved in any of the tests it is drawn to be included in is at most \[\begin{align} \label{eq:prob95resolve95no95tests951} \left(1 - q_{\nu, r} + o(1) \right)^{L_2} &= \exp\left(L_2 \log \left(1 - q_{\nu, r} + o(1)\right)\right) \\ &= \exp\left(- L_2 \log \left(\frac{1}{1 - q_{\nu, r} + o(1)} \right)\right). \end{align}\tag{37}\] Substituting \(L_2 = \frac{\nu T_2}{k}\), taking a union bound over all \(i \in S_{\rm COMP} \setminus S_{\rm DD}\), and trivially upper bounding the size of \(S_{\rm COMP} \setminus S_{\rm DD}\) by \(k\), the probability of any \(i \in S_{\rm COMP} \setminus S_{\rm DD}\) not being resolved by any test is upper bounded by \[\label{eq:prob95not95resolved95ub} k \exp\left(- \frac{\nu T_2}{k} \log \left(\frac{1}{1 - q_{\nu, r} + o(1)}\right)\right).\tag{38}\] Therefore, choosing \[\label{eq:fixed95gamma95T95choice} T_2 = \frac{k\log k}{\nu \log \big(\frac{1}{1 - q_{\nu, r} + o(1)}\big)}\left(1 + \frac{1}{\log \log k}\right)\tag{39}\] suffices to ensure that 38 is upper bounded by \(k^{-1/\log \log k} = o(1)\). Substituting the expression for \(q_{\nu, r}\) in 30 , this simplifies to \[\begin{align} \label{eq:T95295q95sub952} T_2 &= \frac{k \log k}{\nu \log \big(\frac{1}{1 - \nu^{r-1}e^{-\nu}/(r-1)!}\big)}(1+o(1)). \end{align}\tag{40}\] Optimizing over \(\nu\), substituting \(r = \gamma_{\max}\), and summing the number of tests across both batches, it follows that \[\label{eq:large95T95final} T = \Big(\frac{k}{\log 2}\log_2 \frac{n}{k}\Big)(1+o(1)) + \min_{\nu > 0} \frac{k \log k}{\nu \log \big(\frac{1}{1 - \nu^{\gamma_{\max}-1}e^{-\nu}/(\gamma_{\max}-1)!}\big)}(1+o(1))\tag{41}\] tests suffice to ensure \(P_{\rm e} \to 0\), as claimed.

7 Converse Proofs↩︎

7.1 Roadmap↩︎

As discussed in Section 3, the proofs of Theorems 5 and 6 revolve around the concepts of informativeness and masking, which are defined as follows:

Such a concept has been used extensively in the classical group testing literature to prove non-adaptive converse bounds [20], [22], [32], [33], so it is natural to adopt such a strategy in the TGT and GT-ST settings we consider. Intuitively, an item being masked means that it is difficult for any decoder to correctly classify, since its defectivity status is conditionally independent of the test outcomes. Thus, if there are many masked defectives and non-defectives, then any decoder would effectively have to “guess” the status of each of these items, which will fail with high probability. While this is only an intuitive argument, it is formalized in Section 7.2.6.

Thus, we seek to show that for values of \(T\) below that stated in Theorems 5 and 6, there are many masked defectives and non-defectives with high probability. In pursuit of this goal, we make the following simplifying assumptions on \(S\) and \(k\) (to be dropped later) that will be useful in the analysis:

• We assume that \(S\) is generated according to the i.i.d. prior, where each item is defective independently with probability \(q = \frac{k}{n}\).

• Additionally, we assume that the sparsity parameter \(\theta\) is arbitrarily close to \(1\); specifically, \(k = n^{1-\xi}\), where \(\xi > 0\) is arbitrarily small.

Under these assumptions, we demonstrate that there are many masked defectives and non-defectives with high probability via the following high-level roadmap. We will first state it for the simpler proof of Theorem 5 (TGT), and outline the changes made for proving Theorem 6 (GT-ST) in Section 7.3.1.

1. Establish the existence of a set \(\mathcal{I} \subset [n]\) of size \(\lvert \mathcal{I}\rvert \geq n^{1-3\xi}\) whose masking events are independent. This can be found using a greedy construction analogous to that of the Gilbert-Varshamov construction [40].

2. For a given \(i \in \mathcal{I}\) and \(s \in \{0,\dots,d_i\}\) (where we recall that \(d_i\) is the number of tests \(i\) is included in), we seek to obtain a lower bound on the probability of \(L_{s,i}\), where \(L_{s,i}\) is the event that the following both occur: (i) exactly \(s\) of the tests \(i\) is included in contain at most \(\gamma - 2\) other defectives; and (ii) the remaining \(d_i - s\) tests that \(i\) is included in contain at least \(\gamma\) other defectives.

3. Let \(D_i\) denote the event that \(i \in \mathcal{I}\) is masked. The probability of \(D_i\) is then equal to the probability that \(L_{s,i}\) occurs for at least one \(s \in \{0,\dots, d_i\}\). Additionally, the events \(\{L_{s,i}\}_{s=0}^{d_i}\) are mutually disjoint, meaning \(\Pr(D_i)\) can be written as \(\sum_{s=0}^{d_i} \Pr(L_{s,i})\), which can subsequently be lower bounded by the aforementioned bounds on \(\Pr(L_{s,i})\), for each \(s \in \{0,\dots,d_i\}\).

4. We are then able to use the lower bounds on \(\Pr(D_i)\) and the fact that the masking events for each \(i \in \mathcal{I}\) are independent (under the i.i.d. prior) to show that there are many masked items with high probability via a concentration argument. Given this, we can also show that among these masked items, there is at least one masked defective and \(\omega(1)\) masked non-defectives with high probability.

Given these masked items, we will be in a position to show that this implies that successful recovery is not possible, while simultaneously dropping the simplifying assumptions:

1. We remove the first assumption by proving, via a conditioning argument, that the high-probability bound on the number of masked items under the i.i.d. prior extends to the combinatorial prior in the “high-\(\theta\) regime”.

2. Given this, we can show that having at least one masked defective and \(\omega(1)\) masked non-defective implies a success probability of \(o(1)\) for the MAP decoder, which implies the same for any decoder.

3. Finally, we transfer this high-\(\theta\) result to any \(\theta \in (0,1)\) via the contrapositive statement that achievability for smaller \(\theta\) implies achievability for larger \(\theta\) under suitable conditions, importantly showing that this reduction preserves Assumptions 1 and 2.

We now follow this roadmap to give a detailed proof of Theorem 5.

7.2 Proof of Theorem 5 (Converse for the Single-Threshold Setting)↩︎

7.2.1 Step 1 (Constructing \(\mathcal{I}\))↩︎

We begin by constructing a set \(\mathcal{I} \subset [n]\) such that the following properties hold: (i) \(\lvert \mathcal{I}\rvert \geq n^{1-3\xi}\); and (ii) the masking events for all \(i \in \mathcal{I}\) are mutually independent. To this end, we fix an arbitrary non-adaptive test design \(\mathbf{X}\), and represent \(\mathbf{X}\) as a bipartite graph \(G = ([n]\cup [T], E)\), where the edge set \(E \subseteq [n] \times [T]\) is the set consisting of all pairs \((i,t) \in [n] \times [T]\) such that \(X_{ti} = 1\). That is, there is an edge between item \(i \in [n]\) and test \(t \in [T]\) if and only if \(i\) is included in \(t\). Additionally, define the (bipartite) distance between \(i,j \in [n]\) to be minimum number of edges that need to be traversed to reach \(j\) from \(i\). To construct the set \(\mathcal{I}\) satisfying the desired properties, we adopt the following greedy iterative procedure, which follows the ones used in [20], [32] (but with different analysis details to follow):

1. Initialize \(\mathcal{U} = [n]\) and \(\mathcal{I} = \emptyset\).

2. Select an arbitrary item \(i \in \mathcal{U}\), add it to \(\mathcal{I}\), and remove all items from \(\mathcal{U}\) whose distance from \(i\) is at most \(4\) (including \(i\) itself).

3. Repeat Step 2 until \(\mathcal{U} = \emptyset\), and return the set \(\mathcal{I}\).

The following lemma gives a lower bound on the size of the set returned by this procedure, alongside the minimum bipartite distance between items:

Having established that property (i) holds for \(\mathcal{I}\), it now remains to argue that the “minimum distance property” exhibited by the items in \(\mathcal{I}\) implies that their masking events are independent. The key observation is that the masked status of any item \(i \in [n]\) depends only on the set of items that share at least one test with \(i\) (i.e., items with bipartite distance \(2\) of \(i\)). Since any pair of distinct items \(j, j' \in \mathcal{I}\) has distance exceeding \(4\) by construction, the set of items impacting the masking event for \(j\) (i.e., sharing at least one test with \(j\)) is disjoint from those impacting the masking event for \(j'\). This therefore implies that the masking events for all items in \(\mathcal{I}\) are mutually independent, meaning property (ii) also holds for \(\mathcal{I}\).

7.2.2 Step 2 (Lower Bounding \(\Pr(L_{s,i})\))↩︎

We first introduce some notation. For a given item \(i \in [n]\), we define the co-occurrence matrix \(\mathbf{M}^{(i)} \in \{0,1\}^{d_i\times(n-1)}\) to be the sub-matrix of \(\mathbf{X}\) containing the rows \(t \in [T]\) such that \(X_{ti} = 1\), and all columns except for the \(i\)-th one. Thus, the rows of \(\mathbf{M}^{(i)}\) correspond to the tests \(i\) is included in, and the columns denote whether each of the remaining items are included in these tests. Additionally, we define the \(t\)-th defective weight of \(\mathbf{M}^{(i)}\) as \[\label{eq:defective95weight} U_t \mathrel{\vcenter{:}}= \sum_{j \in [n] \setminus \{i\}} \mathbb{1}\{M_{tj}^{(i)} = 1 \wedge j \in S\}\tag{43}\] for each \(t \in [d_i]\), which gives the number of defective items (excluding \(i\)) that are in the \(t\)-th test of \(\mathbf{M}^{(i)}\). In accordance with Definition 4, an item is therefore masked if and only if \(U_t \neq \gamma -1\) for all \(t \in [d_i]\).

Fix an item \(i \in [n]\) and integer \(s \in \{0,\dots,d_i\}\), and recall that the event \(L_{s,i}\) occurs if exactly \(s\) of the tests that \(i\) is included in contain at most \(\gamma - 2\) defectives, and the remaining \(d_i - s\) tests contain at least \(\gamma\) defectives. Using the above definitions, we can equivalently express \(L_{s,i}\) as the event that there is at least one partition \((A, A^c)\) of \([d_i]\) with \(\lvert A \rvert = s\) such that \(U_t \leq \gamma - 2\) for all \(t \in A\) and \(U_t \geq \gamma\) for all \(t \in A^c\). Letting \(\mathcal{A}_{s,i}\) denote the collection of all subsets of \([d_i]\) of size \(s\), and defining the events \[\label{eq:L95plus95minus} L_{A}^- \mathrel{\vcenter{:}}= \bigcap_{t \in A} \{U_t \leq \gamma - 2 \}, \qquad L_A^+ \mathrel{\vcenter{:}}= \bigcap_{t \in A^c} \{U_t \geq \gamma \}\tag{44}\] for each \(A \in \mathcal{A}_{s,i}\), we can thus write \(\Pr(L_{s,i})\) as \[\begin{align} \Pr(L_{s,i}) &= \Pr \left( \bigcup_{A \in \mathcal{A}_{s,i}} \{ L_{A}^- \cap L_{A}^+ \}\right) \\ \label{eq:L95si95new95defn} &= \sum_{A \in \mathcal{A}_{s,i}} \Pr ( L_{A}^- \cap L_{A}^+ ), \end{align}\tag{45}\] where 45 follows since the events \(\{ L_{A}^- \cap L_{A}^+ \}_{A \in \mathcal{A}_{s,i}}\) are mutually disjoint. Note that the test design is fixed, so the probability is only over the randomness in the defective set (under the i.i.d. prior). To derive a lower bound on \(\Pr(L_{s,i})\), we thus begin by lower bounding \(\Pr(L_{A}^- \cap L_{A}^+)\) for each \(A \in \mathcal{A}_{s,i}\). Writing \(\Pr(L_A^- \cap L_A^+) = \Pr(L_A^-) \Pr(L_A^+ \mid L_A^-)\), we proceed to bound each term separately.

Lower Bounding \(\Pr(L_A^-)\). We begin by lower bounding \(\Pr(L_A^-)\). To do so, we note that the events \(\{U_t \leq \gamma - 2\}_{t \in A}\) are decreasing with respect to the items’ defectivity indicator random variables (see Definition 3). Thus, the FKG inequality (Lemma 6) implies that \[\label{eq:FKG95minus} \Pr(L_A^-) = \Pr\left(\bigcap_{t \in A} \{U_t \leq \gamma - 2 \}\right) \geq \prod_{t \in A} \Pr(U_t \leq \gamma - 2).\tag{46}\] Since \(S\) is generated according to the i.i.d. prior (for now), and since test \(t\) includes \(w_t +1\) items, it follows that \(U_t \sim {\rm Bin}(q, w_t)\), where we recall that \(q = \frac{k}{n}\). Thus, \(\Pr(L_A^-)\) can be lower bounded by \[\begin{align} \tag{47} \Pr(L_A^-) &\geq \prod_{t \in A} \Pr ({\rm Bin}(w_t,q) \leq \gamma - 2) \\ \tag{48} &= \prod_{t \in A} \sum_{j=0}^{\gamma - 2} {w_t \choose j} q^j (1-q)^{w_t -j}. \end{align}\]

Lower Bounding \(\Pr(L_A^+ \mid L_A^-).\) We now turn to deriving a lower bound on \(\Pr(L_A^+ \mid L_A^-)\). Doing so directly seems difficult, since the conditioning on \(L_A^-\) means that items in each test may no longer be defective independently. The solution is to only consider the defectivity status of the items that only appear in tests \(t \in A^c\). Clearly, if there are at least \(\gamma\) defectives among these items, the same applies for the entire test pool. Moreover, since any such item is only included in tests \(t \in A^c\), its defectivity status is independent of \(L_A^-\), which only depends on the status of items included in tests \(t \in A\). Combining these assertions thus implies that \[\label{eq:L95plus95lb95init} \Pr( L_A^+ \mid L_A^- ) = \Pr \left(\bigcap_{t \in A^c} \{ U_t \geq \gamma \} \mid L_A^- \right) \geq \Pr\left(\bigcap_{t \in A^c} \{ \widetilde{U}_{t,A} \geq \gamma\}\right),\tag{49}\] where \(\widetilde{U}_{t,A} \leq U_t\) is the number of defective items (excluding \(i\)) that are in test \(t \in A^c\) of \(\mathbf{M}^{(i)}\), and that do not participate in any tests in \(A\). We can now use a similar argument as in the previous case to further lower bound 49 . The main difference here is that events \(\{\widetilde{U}_{t,A} \geq \gamma \}_{t \in A^c}\) are now increasing (Definition 3). Thus, the FKG inequality (Lemma 6) can once again be applied to obtain \[\label{eq:FKG95plus} \Pr\left(\bigcap_{t \in A^c} \{\widetilde{U}_{t,A} \geq \gamma \}\right) \geq \prod_{t \in A^c} \Pr(\widetilde{U}_{t,A} \geq \gamma).\tag{50}\] Denote the number of items in test \(t \in A^c\) that do not appear in any tests in \(A\) by \(z_{t,A}\). Analogous arguments to those in previous section then imply that \(\widetilde{U}_{t,A} \sim {\rm Bin} (z_{t,A}, q)\), which after combining 49 and 50 gives \[\begin{align} \tag{51} \Pr(L_A^+ \mid L_A^-) &\geq \prod_{t \in A^c} \Pr({\rm Bin}(z_{t,A}, q) \geq \gamma) \\ \tag{52} &= \prod_{t \in A^c} \left(1- \sum_{j=0}^{\gamma-1} {z_{t,A} \choose j}q^{j}(1-q)^{z_{t,A} - j} \right). \end{align}\]

Combining Terms. We obtain a lower bound on \(\Pr(L_A^- \cap L_A^+)\) by combining 48 and 52 , which yields \[\label{eq:L95plus95minus95lb} \Pr(L_A^- \cap L_A^+) \geq \left[\prod_{t \in A} \sum_{j=0}^{\gamma - 2} {w_t \choose j} q^j (1-q)^{w_t -j} \right] \cdot \left[\prod_{t \in A^c} \left(1- \sum_{j=0}^{\gamma-1} {z_{t,A} \choose j}q^{j}(1-q)^{z_{t,A} - j} \right)\right].\tag{53}\] Summing Over \(A \in \mathcal{A}_{s,i}\). With this lower bound in place, we are now in a position to lower bound \(\Pr(L_{s,i})\). Taking the sum over all \(A \in \mathcal{A}_{s,i}\), we obtain \[\label{eq:Pr95L95si95lb95init} \Pr(L_{s,i}) \geq \sum_{A \in \mathcal{A}_{s,i}} \left[\prod_{t \in A} \sum_{j=0}^{\gamma - 2} {w_t \choose j} q^j (1-q)^{w_t -j} \right] \cdot \left[\prod_{t \in A^c} \left(1- \sum_{j=0}^{\gamma-1} {z_{t,A} \choose j}q^{j}(1-q)^{z_{t,A} - j} \right)\right],\tag{54}\] which can equivalently be written as⁴ \[\begin{align} \Pr(L_{s,i}) \geq \lvert \mathcal{A}_{s,i}\rvert\frac{1}{\lvert \mathcal{A}_{s,i}\rvert}\sum_{A \in \mathcal{A}_{s,i}} &\exp \Bigg[\sum_{t \in A} \log\Bigg(\sum_{j=0}^{\gamma - 2} {w_t \choose j} q^j (1-q)^{w_t -j}\Bigg) \nonumber \\ \label{eq:equiv95Pr95L95si} &\qquad + \sum_{t \in A^c} \log \Bigg(1- \sum_{j=0}^{\gamma-1} {z_{t,A} \choose j}q^{j}(1-q)^{z_{t,A} - j}\Bigg)\Bigg]. \end{align}\tag{55}\] Using the convexity of the exponential function and Jensen’s inequality, this can be further lower bounded by \[\begin{align} \Pr(L_{s,i}) \geq \lvert \mathcal{A}_{s,i} \rvert &\exp\Bigg[\frac{1}{\lvert \mathcal{A}_{s,i}\rvert} \sum_{A \in \mathcal{A}_{s,i}} \sum_{t \in A} \log\Bigg(\sum_{j=0}^{\gamma - 2} {w_t \choose j} q^j (1-q)^{w_t -j}\Bigg) \nonumber \\ \label{eq:L95si95jensen}&\qquad + \frac{1}{\lvert \mathcal{A}_{s,i}\rvert}\sum_{A \in \mathcal{A}_{s,i}} \sum_{t \in A^c} \log \Bigg(1- \sum_{j=0}^{\gamma-1} {z_{t,A} \choose j}q^{j}(1-q)^{z_{t,A} - j}\Bigg)\Bigg]. \end{align}\tag{56}\] To further lower bound 56 , we define \(z_t \mathrel{\vcenter{:}}= w_t - c(d_{\max}-1)\), and observe the following:

• By Assumptions 1 and 2, each pair of tests shares at most \(c\) items. Consequently, there are at least \(w_t - c(d_i-1) \geq w_t - c(d_{\max} - 1) \eqqcolon z_t\) items (excluding \(i\)) in \(t \in A^c\) that do not appear in any of the remaining \(d_i-1\) tests \(i\) is included in, which implies the same lower bound for \(z_{t,A}\) for all \(A \in \mathcal{A}_{s,i}\) and \(s \in \{0,\dots, d_i\}\).

• The inner sum in the second line of 56 equals \(\Pr({\rm Bin}(z_{t,A}, q) \leq \gamma-1)\). This can therefore be upper bounded by \(\Pr({\rm Bin}(z_t, q) \leq \gamma - 1)\), since the fact that \(z_{t} \leq z_{t,A}\) implies that \({\rm Bin}(z_t, q) \preceq_{\rm st}{\rm Bin}(z_{t,A},q)\) (recall that \(\preceq_{\rm st}\) means “stochastically dominated by”).

Combining these assertions implies that 56 can be lower bounded by \[\begin{align} \Pr(L_{s,i}) \geq \lvert \mathcal{A}_{s,i} \rvert &\exp\Bigg[\frac{1}{\lvert \mathcal{A}_{s,i}\rvert} \sum_{A \in \mathcal{A}_{s,i}} \sum_{t \in A} \log\Bigg(\sum_{j=0}^{\gamma - 2} {w_t \choose j} q^j (1-q)^{w_t -j}\Bigg) \nonumber \\ \label{eq:L95si95zt}&\qquad + \frac{1}{\lvert \mathcal{A}_{s,i}\rvert}\sum_{A \in \mathcal{A}_{s,i}} \sum_{t \in A^c} \log \Bigg(1- \sum_{j=0}^{\gamma-1} {z_{t} \choose j}q^{j}(1-q)^{z_{t} - j}\Bigg)\Bigg]. \end{align}\tag{57}\]

Now, to simplify each of the above double sums, we use the following counting argument. For the first double sum, fix a test \(t \in [d_i]\), and consider the number of sets \(A \in \mathcal{A}_{s,i}\) such that \(t \in A\). Since all sets in \(\mathcal{A}_{s,i}\) are of size \(s\), and since \(t \in A\) by assumption, there are \({d_i - 1 \choose s - 1}\) ways of choosing the remaining items. For the second double sum, a similar argument reveals that there are \({d_i -1 \choose s}\) sets \(A \in \mathcal{A}_{s,i}\) such that \(t \in A^c\) for each \(t \in [d_i]\). Using this, we can therefore express 57 as \[\begin{align} \Pr(L_{s,i}) &\geq \lvert \mathcal{A}_{s,i} \rvert \exp\Bigg[\frac{1}{\lvert \mathcal{A}_{s,i}\rvert} {d_i - 1 \choose s - 1} \sum_{t \in [d_i]} \log\Bigg(\sum_{j=0}^{\gamma - 2} {w_t \choose j} q^j (1-q)^{w_t -j}\Bigg) \nonumber \\ \tag{58}&\qquad \qquad \qquad + \frac{1}{\lvert \mathcal{A}_{s,i}\rvert}{d_i -1 \choose s} \sum_{t \in [d_i]} \log \Bigg(1- \sum_{j=0}^{\gamma-1} {z_t \choose j}q^{j}(1-q)^{z_t - j}\Bigg)\Bigg] \\ \tag{59} &= {d_i \choose s} \exp \Bigg[\frac{s}{d_i} \sum_{t \in [d_i]} \log\Bigg(\sum_{j=0}^{\gamma - 2} {w_t \choose j} q^j (1-q)^{w_t -j}\Bigg) \nonumber \\ &+ \frac{d_i - s}{d_i} \sum_{t \in [d_i]}\log \Bigg(1- \sum_{j=0}^{\gamma-1} {z_t \choose j}q^{j}(1-q)^{z_t - j}\Bigg)\Bigg], \end{align}\] where 59 uses \(\lvert \mathcal{A}_{s,i}\rvert = {d_i \choose s}\). Finally, basic algebraic manipulations give a final lower bound of \[\label{eq:final95L95si95lb} \Pr(L_{s,i}) \geq {d_i \choose s} \left[\prod_{t \in [d_i]} \sum_{j=0}^{\gamma-2}{w_t \choose j} q^j (1-q)^{w_t -j}\right]^{\frac{s}{d_i}} \left[\prod_{t \in [d_i]} \left(1 - \sum_{j=0}^{\gamma-1} {z_t \choose j}q^{j}(1-q)^{z_t - j} \right)\right]^{\frac{d_i - s}{d_i}}.\tag{60}\]

7.2.3 Step 3 (Lower Bounding \(\Pr(D_i)\))↩︎

We are now in a position to lower bound \(\Pr(D_i)\) (i.e., the probability that \(i\) is masked). Recalling Definition 4, an item \(i \in [n]\) is masked if there are no tests that \(i\) is included in that contain exactly \(\gamma -1\) defectives (excluding \(i\)). It follows that \(i\) is masked if and only if \(L_{s,i}\) occurs for at least one \(s \in \{0,\dots, d_i\}\). Using this and the fact that the events \(\{L_{s,i}\}_{s=0}^{d_i}\) are mutually disjoint, \(\Pr(D_i)\) can be written as \(\Pr(D_i) = \sum_{s=0}^{d_i} \Pr(L_{s,i})\). Substituting in the lower bound on \(\Pr(L_{s,i})\) for each \(s \in \{0,\dots,d_i\}\) and using the binomial formula, this can be lower bounded by \[\begin{align} \tag{61} \Pr(D_i) &\geq \sum_{s=0}^{d_i} {d_i \choose s} \left[\prod_{t \in [d_i]} \sum_{j=0}^{\gamma-2}{w_t \choose j} q^j (1-q)^{w_t -j}\right]^{\frac{s}{d_i}} \left[\prod_{t \in [d_i]} \left(1 - \sum_{j=0}^{\gamma-1} {z_t \choose j}q^{j}(1-q)^{z_t - j} \right)\right]^{\frac{d_i - s}{d_i}} \\ \tag{62} &= \left[ \left(\prod_{t \in [d_i]} \sum_{j=0}^{\gamma-2}{w_t \choose j} q^j (1-q)^{w_t -j}\right)^{\frac{1}{d_i}} + \left(\prod_{t \in [d_i]} \left(1 - \sum_{j=0}^{\gamma-1} {z_t \choose j}q^{j}(1-q)^{z_t - j} \right)\right)^{\frac{1}{d_i}}\right]^{d_i}. \end{align}\] To further lower bound this, we focus our attention on each of the sums in 62 . Namely, we wish to lower bound the summation in the first term, and upper bound the summation in the second term, for each \(t \in [d_i]\). We begin with the former. To do so, note that this sum equals \(\Pr({\rm Bin}(w_t, q) \leq \gamma -2)\), which implies that it is lower bounded by \(\Pr({\rm Bin}(w_{\max}, q )\leq \gamma -2 )\), since \({\rm Bin}(w_t, q) \preceq_{\rm st}{\rm Bin}(w_{\max}, q)\) for all \(t \in [d_i]\). Thus, it follows that \[\label{eq:first95sum95lb} \sum_{j=0}^{\gamma - 2}{w_t \choose j}q^j(1-q)^{w_t - j} \geq \sum_{j=0}^{\gamma - 2} {w_{\max} \choose j}q^j(1 -q)^{w_{\max} - j}\tag{63}\] for all \(t \in [d_i]\). Using an analogous argument for the second sum in 62 gives an upper bound of \[\label{eq:second95sum95lb} \sum_{j=0}^{\gamma-1} {z_t \choose j}q^{j}(1-q)^{z_t - j} \leq \sum_{j=0}^{\gamma-1} {z_{\min} \choose j}q^{j}(1-q)^{z_{\min} - j},\tag{64}\] for all \(t \in [d_i]\) where \(z_{\min} := w_{\min} - c(d_{\max}-1)\) (with \(w_{\min} \mathrel{\vcenter{:}}= \min_{t \in [T]}w_t\)) is a uniform lower bound on \(z_t\). Substituting these bounds back into 62 and simplifying, alongside using \(d_i \leq d_{\max}\), we obtain \[\label{eq:Pr95Di95lb953} \Pr(D_i) \geq \left[\sum_{j=0}^{\gamma-2}{w_{\max} \choose j}q^j(1 -q)^{w_{\max} - j} + 1 - \sum_{j=0}^{\gamma-1} {z_{\min} \choose j}q^{j}(1-q)^{z_{\min}- j}\right]^{d_{\max}}.\tag{65}\] To obtain our final bound on \(\Pr(D_i)\) for all \(i \in [n]\), we derive an upper bound on \(d_{\max}\) in terms of \(T\). A double counting argument reveals that \(\sum_{i=1}^n d_i = \sum_{t=1}^T (w_t+1)\), which in turn implies that \(n d_{\min} \leq T (w_{\max}+1)\), with \(d_{\min} \mathrel{\vcenter{:}}= \min_{i \in [n]}d_i\). Using Assumption 1, we also have the bound \(n d_{\min} \geq \frac{n d_{\max}}{\zeta}\). Combining these, we obtain a final lower bound for \(\Pr(D_i)\) of \[\label{eq:Pr95Di95lb95final} \Pr(D_i) \geq \left[\sum_{j=0}^{\gamma-2}{w_{\max} \choose j}q^j(1 -q)^{w_{\max} - j} + 1 - \sum_{j=0}^{\gamma-1} {z_{\min} \choose j}q^{j}(1-q)^{z_{\min}- j}\right]^{\frac{\zeta T(w_{\max}+1)}{n}}.\tag{66}\]

7.2.4 Step 4 (Lower Bounding the Number of Masked Items, i.i.d. Prior)↩︎

Given the set \(\mathcal{I}\) and the lower bound on \(\Pr(D_i)\) for all \(i \in [n]\), we are now in a position to derive a high-probability lower bound on the number of masked items, which we denote by \(M\). Recall that by construction, \(\mathcal{I}\) has size at least \(n^{1-3\xi}\), and the items in \(\mathcal{I}\) have mutually independent masking events. Using this and the lower bound on \(\Pr(D_i)\), it follows that \({\rm Bin}(n^{1-3\xi}, \Xi^{\frac{\zeta T (w_{\max}+1)}{n}}) \preceq_{\rm st}M\), where \(\Xi \in [0,1]\) is the term inside the exponent in 66 . The expected value of the binomial random variable is given by \[\label{eq:avg95num95binom} n^{1-3\xi} \Xi^{\frac{\zeta T (w_{\max}+1)}{n}} = n^{1-3\xi} \exp\left( \frac{\zeta T (w_{\max}+1)}{n} \log (\Xi)\right),\tag{67}\] which is at least \(n^{2\xi}\) whenever \[\label{eq:n952xi95avg95T} T \leq \frac{n \log n}{-\zeta (w_{\max}+1) \log (\Xi)}(1 - 5\xi).\tag{68}\] Substituting the definition of \(\Xi\) and writing \(n = k^{\frac{1}{1-\xi}}\), this condition becomes \[\label{eq:Lambda95def95avg95T} T \leq \frac{n\log k}{\displaystyle-\zeta (w_{\max}+1) \log \left(\sum_{j=0}^{\gamma-2}{w_{\max} \choose j}q^j(1 -q)^{w_{\max} - j} + 1 - \sum_{j=0}^{\gamma-1} {z_{\min} \choose j}q^{j}(1-q)^{z_{\min}- j}\right)}(1-\varepsilon),\tag{69}\] where \(\varepsilon > 0\) is an arbitrarily small constant (depending on arbitrarily small \(\xi > 0\)). To further simplify this, recall that \(\frac{c \cdot d_{\max}}{w_{\min}} = o(1)\) via Assumption 2, which in turn implies that \(z_{\min} = w_{\min}(1 - o(1))\). Additionally, we have due to Assumption 1 that \(w_{\min}=\frac{\Delta n}{k}(1-o(1))\), \(w_{\max}+1 = \frac{\Delta n}{k}(1+o(1))\) and \(\zeta = 1+o(1)\), which combined with the fact that \(q = \frac{k}{n}\) means we can apply a Poisson approximation (Lemma 5) to obtain \[\begin{align} \tag{70} T &\leq \frac{k \log k}{\displaystyle- \Delta\log \left(\sum_{j=0}^{\gamma - 2}\frac{\Delta^j e^{-\Delta}}{j!} + 1 - \sum_{j=0}^{\gamma - 1} \frac{\Delta^je^{-\Delta}}{j!}\right)}(1-\varepsilon)(1-o(1)) \\ \tag{71} &= \frac{k \log k}{\displaystyle- \Delta \log\left(1 - \frac{\Delta^{\gamma - 1}e^{-\Delta}}{(\gamma - 1)!}\right)}(1-\varepsilon)(1-o(1)), \end{align}\] since the sums in the denominator of 69 each correspond to a binomial CDF. Absorbing the \(1-o(1)\) term into \(\varepsilon\) (when \(n\) is large enough) and minimizing over \(\Delta\), it follows that 67 is at least \(n^{2\xi}\) for all \(\Delta > 0\) as long as \[\label{eq:optimised95avg95T} T \leq \min_{\Delta > 0} \frac{k \log k}{\displaystyle- \Delta\log\left(1 - \frac{\Delta^{\gamma - 1}e^{-\Delta}}{(\gamma - 1)!}\right)}(1-\varepsilon).\tag{72}\]

If 72 holds, then the Chernoff bound (Lemma 3) alongside the fact that \({\rm Bin}(n^{1-3\xi}, \Xi^{\frac{\zeta T (w_{\max}+1)}{n}}) \preceq_{\rm st}M\) gives \[\label{eq:total95masked95lb95whp}\Pr\left(M \leq \frac{1}{2}n^{2\xi}\right) \leq \Pr\left({\rm Bin}(n^{1-3\xi}, \Xi^{\frac{\zeta T (w_{\max}+1)}{n}}) \leq \frac{1}{2}n^{2\xi}\right) \leq \exp(-\Omega(n^{2\xi})).\tag{73}\]

Conditioned on \(M \geq \frac{1}{2}n^{2\xi}\), we now seek to obtain lower bounds on \(M_0\) and \(M_1\), the number of masked non-defective and masked defective items respectively. We begin with \(M_0\). Since a given masked item’s defectivity status is conditionally independent of the test outcomes (given the masking event), its posterior probability of being defective matches its prior (i.e., it remains defective with probability \(q = \frac{k}{n}\)), which can easily be seen via an application of Bayes’ theorem (and is used in [20], [32]). Moreover, the independent masking events of each \(i \in \mathcal{I}\) imply that each of the masked items in \(\mathcal{I}\) are defective independently of one another. Thus, we obtain \({\rm Bin}(\frac{1}{2}n^{2\xi}, 1-q) \preceq_{\rm st}(M_0 \mid M \geq \frac{1}{2}n^{2\xi})\), which in turn implies via the Chernoff bound that \[\label{eq:M95095lb} \Pr\left(M_0 \leq \frac{1}{4}n^{2\xi} \mid M \geq \frac{1}{2}n^{2\xi}\right) \leq \Pr\left({\rm Bin}\Big(\frac{1}{2}n^{2\xi}, 1 - q\Big) \leq \frac{1}{4}n^{2\xi}\right) \leq \exp(-\Omega(n^{2\xi})).\tag{74}\] Using a similar argument for \(M_1\), the probability of there being no masked defectives can be upper bounded by \[\label{eq:Pr95no95masked95defs} \Pr\left(M_1 = 0 \mid M \geq \frac{1}{2}n^{2\xi}\right) \leq \left(1 - \frac{k}{n}\right)^{\frac{1}{2}n^{2\xi}} = \left(1 -\frac{1}{n^{\xi}}\right)^{\frac{1}{2}n^{2\xi}} \leq e^{-\frac{1}{2}n^{\xi}}.\tag{75}\] Defining \(\mathcal{E} = \{M_0 \leq \frac{1}{4}n^{2\xi}\} \cup \{M_1 = 0\}\), we can use the law of total probability and 73 , alongside a union bound, to obtain \[\begin{align} \tag{76} \Pr(\mathcal{E}) &\leq \Pr\left(\mathcal{E} \mid M \geq \frac{1}{2}n^{2\xi} \right) + \exp(-\Omega(n^{2\xi})) \\ \tag{77} &\leq \Pr\left(M_0 \leq \frac{1}{4}n^{2\xi} \mid M \geq \frac{1}{2}n^{2\xi}\right) + \Pr\left(M_1 = 0 \mid M \geq \frac{1}{2}n^{2\xi}\right) + \exp(-\Omega(n^{2\xi})) \\ \tag{78} &= \exp(-\Omega(n^\xi)). \end{align}\]

7.2.5 Step 5 (Transferring from i.i.d. Prior to Combinatorial Prior)↩︎

In the previous step, we showed that under the i.i.d. prior, there were at least \(\frac{1}{4}n^{2\xi}\) masked non-defectives and at least one masked defective with probability \(1 - \exp(-\Omega(n^\xi))\). To obtain a similar guarantee under the combinatorial prior, we use the fact that for any event \(\mathcal{F}\), \[\begin{align} \tag{79} \Pr\nolimits_{\rm c}(\mathcal{F}) &= \Pr\nolimits_{{{\rm i.i.d.}}}(\mathcal{F} \mid \{\lvert S \rvert = k\}) \\ \tag{80} &\leq \frac{\Pr_{\rm i.i.d.}(\mathcal{F})}{\Pr_{\rm i.i.d.}(\lvert S \rvert = k)}, \end{align}\] where \(\Pr_{\rm c}\) and \(\Pr_{\rm i.i.d.}\) are the probability measures under the combinatorial and i.i.d. priors respectively. Applying this with the event \(\mathcal{E}\) and using its aforementioned upper bound under the i.i.d. prior, its probability under the combinatorial prior is upper bounded by \[\label{eq:Pr95E95comb95ub95init} \Pr\nolimits_{\rm c}(\mathcal{E}) \leq \frac{\exp(-\Omega(n^\xi))}{\Pr_{\rm i.i.d.}(\lvert S \rvert = k)},\tag{81}\] which means that showing \(\Pr_{\rm c}(\mathcal{E}) = o(1)\) amounts to showing that \(\Pr_{\rm i.i.d.}(\lvert S \rvert = k)\) is “not too small”. Under the i.i.d. prior with \(q=\frac{k}{n}\), this probability is given by \[\label{eq:Pr95iid95S95eq95k} \Pr\nolimits_{\rm i.i.d.}(\lvert S \rvert = k) = {n \choose k}\left(\frac{k}{n}\right)^{k}\left(1 - \frac{k}{n}\right)^{n-k} = {n \choose k} \exp(-nH(k/n)),\tag{82}\] where \(H(\cdot)\) denotes the binary entropy function measured in nats. Using Lemma 7, this can be lower bounded by \[\begin{align} \tag{83} \Pr\nolimits_{\rm i.i.d.}(\lvert S \rvert = k) &\geq \frac{\exp(n H(k/n))}{2\sqrt{2k(1-k/n)}} \exp(-nH(k/n)) \\ \tag{84} &\geq \frac{1}{2 \sqrt{2k}}. \end{align}\] Thus, \(\Pr_{\rm c}(\mathcal{E})\) can be upper bounded by \[\label{eq:Pr95E95comb95ub95final} \Pr\nolimits_{\rm c}(\mathcal{E}) \leq 2\sqrt{2k} \exp(-\Omega(n^\xi)) = o(1),\tag{85}\] which gives the desired result.

7.2.6 Step 6 (Lower Bounding the Error Probability, High-\(\theta\) Regime)↩︎

Having established that \(\mathcal{E}^c\) holds with probability \(1-o(1)\) under the combinatorial prior, we are now able to derive a lower bound on the error probability when \(k = n^{1-\xi}\). To do so, we first introduce the notion of satisfying sets:

Before proceeding, we state some known facts:

• Denoting \(\mathcal{V}(\mathbf{X}, \mathbf{y})\) as the collection of all satisfying sets of size \(k\), the posterior distribution of \(S\) given \((\mathbf{X}, \mathbf{y})\) is uniform over \(\mathcal{V}(\mathbf{X}, \mathbf{y})\) (e.g., see [20]).⁵

• The maximum a posteriori (MAP) decoder is optimal among all decoders; in view of the first dot point, it returns an arbitrary (or possibly randomly-chosen) element of \(\mathcal{V}(\mathbf{X}, \mathbf{y})\), thus being correct with conditional probability \(\frac{1}{|\mathcal{V}(\mathbf{X}, \mathbf{y})|}\) (given \(\mathcal{V}(\mathbf{X}, \mathbf{y})\)).

• It was also shown in [20] that \(\lvert \mathcal{V}(\mathbf{X}, \mathbf{y})\rvert \geq M_0 \cdot M_1\); this is because the true defective set \(S\) is satisfying by definition, and a new satisfying set \(S'\) can be formed by swapping out a single masked defective item with a masked non-defective item. Since there are \(M_0 \cdot M_1\) ways of performing such a swap, the claim follows.

Combining these observations, the success probability of the MAP decoder (and thus any decoder \(\hat{S}\)) is upper bounded by \[\label{eq:succ95prob95ub} \Pr(\hat{S} = S \mid (M_0,M_1) = (m_0,m_1)) \leq \frac{1}{\lvert \mathcal{V}(\mathbf{X}, \mathbf{y})\rvert } \leq \frac{1}{m_0 \cdot m_1}.\tag{86}\] Conditioned on \(\mathcal{E}^c\), we have \(M_1 \geq 1\) and \(M_0 \geq \frac{1}{4}n^{2\xi}\) by definition. Combining this with law of total probability and the fact that \(\Pr(\mathcal{E}) = o(1)\), the success probability of any decoder is upper bounded by \[\begin{align} \tag{87} \Pr(\hat{S} = S) &= \Pr(\{\hat{S} = S\} \cap \mathcal{E}) + \Pr(\{\hat{S} = S\} \cap \mathcal{E}^c) \\ \tag{88} &\leq o(1) +\frac{4}{n^{2\xi}} \\ \tag{89} &= o(1). \end{align}\] Thus, any decoder fails with probability approaching \(1\) in the “dense” regime \(k = n^{1-\xi}\) whenever \(T\) satisfies 72 .

7.2.7 Step 7 (Transferring from High \(\theta\) to Low \(\theta\))↩︎

In the previous step, we showed that under the combinatorial prior, any decoder fails with probability \(1-o(1)\) when \(k = n^{1-\xi}\) (i.e., when \(\theta\) is arbitrarily close to one). To conclude the proof of Theorem 5, it remains to transfer this converse result from \(\theta\) arbitrarily close to one to any \(\theta \in (0,1)\). In what follows, we will denote quantities in the “dense” regime with a prime superscript (e.g., \(n', \theta',\mathbf{X}'\)), and quantities in the “sparse” regime without this (e.g., \(n, \theta, \mathbf{X}\)). Quantities that remain the same in both regimes (e.g., \(k\)) will retain their original notation. Thus, the test design \(\mathbf{X}\) in the previous steps is now written as \(\mathbf{X}'\), and the relationship between number of defectives \(k\) and the population size in the dense regime is \(k = (n')^{\theta'} = (n')^{1-\xi}\). To establish the reduction from the denser regime to the sparser regime, we follow the argument of [20] (see also [22]), who proved the result via its contrapositive: an achievability result for a given \(\theta\) implies the same for any larger \(\theta' > \theta\), provided the two problems share the same \(k\) but have different population sizes, and the number of tests scales as \(T = c k \log k\) for some \(c > 0\). This can be done by starting with a test design \(\mathbf{X}\in \{0,1\}^{T\times n}\) for the sparse regime with \(n\) items and \(k = \Theta(n^\theta)\) defectives, and constructing a test design \(\mathbf{X}' \in \{0,1\}^{T\times n'}\) for the dense regime with \(n' \ll n\) items and \(k = (n')^{\theta'}\) defectives for \(\theta' > \theta\) as follows:

1. Choose a subset \(W \subset [n]\) of size \(\lvert W \rvert = n'\) uniformly at random from the \({n \choose n'}\) possibilities, and declare the items in \([n] \setminus W\) to be (dummy) non-defectives.

2. Map the items in \([n']\) to \(W\) in an arbitrary manner (e.g., in numerical order).

3. Construct \(\mathbf{X}' \in \{0,1\}^{T \times n'}\) by taking it as the sub-matrix of \(\mathbf{X}\) with the columns indexed by \(W\).

4. Perform the tests according to \(\mathbf{X}'\) and observe the induced test outcome result vector \(\mathbf{y}'\).

Observe that since the items in \([n] \setminus W\) are non-defective by construction, the test outcome vectors \(\mathbf{y}\) and \(\mathbf{y}'\) generated by \(\mathbf{X}\) and \(\mathbf{X}'\) respectively are identical. Additionally, the symmetry of the construction of \(\mathbf{X}'\) implies that if there are \(k\) defectives in \([n']\) uniformly at random, the same applies to \([n]\). Thus, any decoder that achieves \(\Pr(\hat{S} \neq S) \to 0\) using the test design \(\mathbf{X}\) also does so using \(\mathbf{X}'\), which gives the desired result.

To conclude the proof, we show that constructing \(\mathbf{X}'\) in the manner described above leads to Assumptions 1 and 2 still holding with probability \(1-o(1)\) for \(\theta'\) sufficiently close to \(1\) (assuming \(\mathbf{X}\) satisfies them), as the previous steps relied on these assumptions. Since \(\mathbf{X}'\) is formed by taking a subset of the columns of \(\mathbf{X}\), the values of \(d_i\) in the columns in \(\mathbf{X}'\) are equivalent to their corresponding columns in \(\mathbf{X}\), meaning that if the values of \(d_i\) in \(\mathbf{X}\) satisfy Assumption 1, the same applies for the corresponding values of \(d_i\) in \(\mathbf{X}'\). Thus, to show that both assumptions still hold, we need to show (with high probability) that the test weights and pairwise test overlaps in \(\mathbf{X}'\) satisfy the conditions in Assumptions 1-2, which can be done via the following concentration arguments:

Concentration of Test Weights. Fix a test \(t \in \{1,\dots,T\}\) with test weight \(w_t+1 = \frac{\Delta_t n}{k}\), where \(\Delta_t \in [\Delta - o(1), \Delta + o(1)]\) due to Assumption 1. Since \(\mathbf{X}'\) is formed by choosing \(n'\) columns uniformly at random from \(\mathbf{X}\), the (random) test weight of the \(t\)-th test in \(\mathbf{X}'\) is distributed as \(W_t' \sim {\rm HypGeo}(n, \frac{\Delta_t n}{k}, n')\), with mean \(w_t' \mathrel{\vcenter{:}}= \mathbb{E}[W_t'] = \frac{\Delta_t n'}{k}\) (for notational convenience, we denote the test weight in the reduced test matrix as \(W_t'\) rather than \(W_t' + 1\) here; the shift by 1 is a lower-order asymptotic term). To obtain a high-probability bound on \(W_t\), we use the fact that the Chernoff bound (Lemma 3) also holds for hypergeometric random variables to obtain \[\label{eq:w95t3995conc} \Pr(\lvert W_t' - w_t'\rvert \geq \delta w_t') \leq 2\exp\left(-\frac{\delta^2 w_t'}{3}\right)\tag{90}\] for any \(\delta \in (0,1)\). Since \(w_t' = n^{\Omega(1)}\), the choice \(\delta = \frac{1}{\log n}\) ensures that \(W_t' \notin (w_t'(1- o(1)), w_t'(1+o(1)))\) with probability \(\exp(-n^{\Omega(1)})\). Since this holds for any \(t \in [T]\), a union bound over all \(T = O(k \log n)\) tests implies that the probability that \(W_t' \notin (w_t'(1-o(1)), w_t'(1+o(1))\) for any \(t \in [T]\) is also \(\exp(-n^{\Omega(1)})\). Substituting in the value of \(w_t'\), we obtain \[\label{eq:W95t3995range95whp} W'_t \in \left(\frac{\Delta_t n'}{k}(1-o(1)), \frac{\Delta_t n'}{k}(1+o(1))\right), \;\forall t \in [T]\tag{91}\] with probability \(1-o(1)\). Finally, the fact that \(\Delta_t \in [\Delta - o(1), \Delta + o(1)]\) for all \(t\) implies that \[\label{eq:w95t3995min95max} \min_{t \in [T]} W_t'= \frac{\Delta n'}{k}(1-o(1)), \quad \max_{t \in [T]} W_t' = \frac{\Delta n'}{k}(1+o(1))\tag{92}\] with probability \(1-o(1)\), meaning that Assumption 1 is satisfied for \(\mathbf{X}'\).

Concentration of Test Overlaps. Fix a pair of tests \((i,j) \in [T]^2\), and denote by \(c_{ij}\) the number of items appearing in both tests in \(\mathbf{X}\). By a similar argument to the previous case, the (random) number of items appearing in both tests in \(\mathbf{X}'\) is distributed as \(C_{ij}' \sim {\rm HypGeo}(n, c_{ij}, n')\). Since Assumption 2 gives \(c_{ij} \leq c\) for all \((i,j) \in [T]^2\), it follows that \(C_{ij}' \preceq_{\rm st}{\rm HypGeo}(n, c, n')\). Recalling the assumption \(c = o\big( \frac{n}{k \log n} \big)\), it follows that \(\mu_{ij} := \mathbb{E}[C'_{ij}] \le \frac{c n'}{n} = o\big( \frac{n'}{k \log n} \big)\). Since \(k=(n')^{1-\xi}\) and \(\log n' = \Theta(\log n)\), it follows that the quantity \[b_n:=\frac{n'}{k\log n'}=\frac{(n')^\xi}{\log n'}\] grows polynomially in \(n'\). We fix an arbitrary sequence \(a_n\) satisfying both \(a_n\gg \log n\) and \[\max_{i,j}\mu_{ij}\ll a_n\ll b_n.\] Then, applying the Chernoff bound for the hypergeometric distribution, this time in the strengthened form \[\Pr(C'_{ij}\ge a_n) \le \left(\frac{e\mu_{ij}}{a_n}\right)^{a_n},\] we obtain \[\Pr(C'_{ij}\ge a_n)\le \exp(-\omega(\log n)).\] Taking a union bound over \(O(T^2)=O(k^2\log^2 n)\) pairs of tests then gives the following for all \((i,j)\) with probability \(1-o(1)\): \[\max_{i\neq j} C'_{ij}\le a_n = o\Big(\frac{n'}{k\log n'}\Big).\] Thus, Assumption 2 is also satisfied for \(\mathbf{X}'\).

7.2.8 Wrapping Up↩︎

Combining the findings from Steps 1-7, we can conclude that under the combinatorial prior, the error probability tends to \(1\) for any decoder \(\hat{S}\), sparsity parameter \(\theta\), and test design \(\mathbf{X}\) satisfying Assumptions 1-2, as long as 72 holds. Thus, to ensure that \(\Pr(\hat{S} \neq S) \nrightarrow 1\), we require that \[\label{eq:required95T95single} T \geq \min_{\Delta > 0} \frac{k \log k}{-\displaystyle\Delta \log \left(1 - \frac{\Delta^{\gamma - 1}e^{-\Delta}}{(\gamma - 1)!}\right)}(1-o(1)).\tag{93}\] This completes the proof of Theorem 5.

7.3 Proof of Theorem 6 (Converse for the Selectable-Threshold Setting)↩︎

7.3.1 Outline of Modifications↩︎

When handling the more general GT-ST problem, we can broadly use the same proof template, with many of the steps being exactly the same as in the single-threshold setting. In particular, we follow a similar 7-step roadmap to the one detailed in Section 7.1. Of these steps, we outline those that proceed in the same manner as before, and those that require modification:

• Steps 1 and 5-7 proceed identically as in the single-threshold converse, both in their description and analysis. We therefore omit the details here and refer the reader to Section 7.1 for their descriptions, and Sections 7.2.1 and 7.2.5-7.2.7 for their analyses.

• The description of Step 4 is the same in both cases; however, the subsequent analyses differ. Thus, we include a detailed analysis of this step for the selectable-threshold case in Section 7.3.4, while not repeating its description.

• Adapting Steps 2 and 3 to the selectable-threshold setting requires modifications of both their descriptions and subsequent analyses.

We now outline these modifications made to Steps 2 and 3:

• Fix \(i \in \mathcal{I}\) and \(\mathbf{s} = (s_{1}, \dots, s_{\ell})\in \mathcal{S}_i \mathrel{\vcenter{:}}= \{0,\dots, d_{i,1}\} \times \cdots \times \{0,\dots, d_{i,\ell}\}\), where for each \(r \in [\ell]\), \(d_{i,r}\) is the number of tests with threshold \(\gamma_r\) that item \(i\) appears in. We seek to lower bound \(\Pr(L_{\mathbf{s},i})\), where \(L_{\mathbf{s},i}\) is the event that the following both occur for all \(r \in [\ell]\): (i) exactly \(s_r\) of the tests with threshold \(\gamma_r\) that \(i\) is included in contain at most \(\gamma_r - 2\) other defectives; and (ii) the remaining \(d_{i,r} - s_r\) tests with threshold \(\gamma_r\) that \(i\) is included in contain at least \(\gamma_r\) other defectives.

• In the selectable-threshold setting, the probability of \(D_i\) (i.e., the event that \(i\) is masked) can then be written as \(\Pr(D_i) = \sum_{\mathbf{s} \in \mathcal{S}_i}\Pr(L_{\mathbf{s},i})\), analogous to its definition in Step 3 in the single-threshold setting (which involved a sum of the probabilities of \(L_{s,i}\) over \(s \in \{0,\dots, d_i\}\)). We can then use the previously derived lower bounds on \(\Pr(L_{\mathbf{s},i})\) to lower bound \(\Pr(D_i)\), similarly to the single-threshold setting.

The above changes can be seen as a direct generalization of Steps 2 and 3 to the selectable-threshold setting, so one would expect their respective analyses to exhibit a similar form to their single-threshold counterparts. Indeed, this is the case, with the details provided below.

7.3.2 Step 2: Lower Bounding \(\Pr(L_{\mathbf{s}, i})\)↩︎

As discussed above, the approach here is similar to that of Section 7.2.2, and can be seen as a direct generalization of the methods therein. Namely, for a given \(i \in [n]\) and \(\mathbf{s} = (s_1,\dots, s_\ell) \in \mathcal{S}_i\), we wish to derive a lower bound on the probability that among the tests with threshold \(\gamma_r\) in which \(i\) is included in, exactly \(s_r\) tests contain at most \(\gamma_r - 2\) other defectives, with the remaining \(d_{i,r} -s_r\) tests containing at least \(\gamma_r\) other defectives, for all \(r \in [\ell]\). To formalize this, we first introduce some definitions, analogous to those given in Section 7.2.2:

• We define \(\mathbf{M}^{(i)}_r \in \{0,1\}^{d_{i,r}\times (n-1)}\) similarly to \(\mathbf{M}^{(i)}\), except that \(\mathbf{M}_r^{(i)}\) only consists of tests that \(i\) is included in with threshold \(\gamma_r\), rather than all tests \(i\) is included in. Thus, each row represents a test including item \(i\) with threshold \(\gamma_r\), with its \(n-1\) entries indicating the presence/absence of the remaining items.

• Similarly, the \(t_r\)-th defective weight of \(\mathbf{M}_r^{(i)}\), denoted by \(U_{t_r}\), is the number of defective items (excluding \(i\)) that appear in test \(t_r \in [d_{i,r}]\) with threshold \(\gamma_r\).

• We define \(\mathcal{A}_{s_r,i}\) as the collection of all subsets of \([d_{i,r}]\) of size \(s_r\).

• For a given \(r \in [\ell]\) and \(A_r \in \mathcal{A}_{s_r,i}\), the events \(L_{A_r}^-, L_{A_r}^+\) are defined analogously to 44 as follows: \[\label{eq:L95plus95minus95multi} L_{A_r}^- \mathrel{\vcenter{:}}= \bigcap_{t_r \in A_r} \{U_{t_r} \leq \gamma_r - 2 \}, \qquad L_{A_r}^+ \mathrel{\vcenter{:}}= \bigcap_{t_r \in A_r^c} \{U_{t_r} \geq \gamma_r \},\tag{94}\] where \(A_r^c \mathrel{\vcenter{:}}= [d_{i,r}] \setminus A_r\). In particular, we note that, like their single-threshold counterparts, \(L_{A_r}^-, L_{A_r}^+\) are intersections of decreasing and increasing events, respectively, for all \(r \in [\ell]\).

• Furthermore, we define \(\mathcal{A}_{\mathbf{s},i} = \mathcal{A}_{s_1,i} \times \cdots \times \mathcal{A}_{s_\ell,i}\), and let \[\label{eq:L95bfA95plus95minus} L_{\mathbf{A}}^- \mathrel{\vcenter{:}}= \bigcap_{r \in [\ell]} L_{A_r}^-, \qquad L_{\mathbf{A}}^+ \mathrel{\vcenter{:}}= \bigcap_{r \in [\ell]} L_{A_r}^+\tag{95}\] for each \(\mathbf{A} \in \mathcal{A}_{\mathbf{s}, i}\).

Given these definitions, we can thus express \(\Pr(L_{\mathbf{s},i})\) as \[\begin{align} \Pr(L_{\mathbf{s},i}) &= \Pr\left(\bigcup_{\mathbf{A} \in \mathcal{A}_{\mathbf{s},i}} \{L_{\mathbf{A}}^- \cap L_{\mathbf{A}}^+ \}\right) \\ \label{eq:Pr95L95bfs95i} & =\sum_{\mathbf{A} \in \mathcal{A}_{\mathbf{s},i}} \Pr(L_{\mathbf{A}}^- \cap L_\mathbf{A}^+), \end{align}\tag{96}\] with 96 following since the events \(\{L_{\mathbf{A}}^- \cap L_{\mathbf{A}}^+\}_{\mathbf{A} \in \mathcal{A}_{\mathbf{s},i}}\) are mutually disjoint. As in Section 7.2.2, we first focus on bounding \(\Pr(L_{\mathbf{A}}^- \cap L_{\mathbf{A}}^+) = \Pr(L_{\mathbf{A}}^-)\Pr(L_\mathbf{A}^+ \mid L_{\mathbf{A}}^-)\) for each \(\mathbf{A} \in \mathcal{A}_{\mathbf{s},i}\).

Lower Bounding \(\Pr(L_{\mathbf{A}}^-)\). Since, as noted above, the events \(L_{A_r}^-\) are intersections of decreasing events for all \(r \in [\ell]\), the FKG inequality (Lemma 6) gives \[\label{eq:L95bfA95minus95lb} \Pr(L_{\mathbf{A}}^-) \geq \prod_{r \in [\ell]} \prod_{t_r \in A_r} \Pr(U_{t_r} \leq \gamma_r - 2).\tag{97}\] Analogously to the single-threshold setting, each \(U_{t_r}\) has distribution \(U_{t_r} \sim {\rm Bin}(w_{t_r}, q)\), meaning 97 can be written as \[\label{eq:Pr95L95bfA95minus95bino} \Pr(L_{\mathbf{A}}^-) \geq \prod_{r \in [\ell]} \prod_{t_r \in A_r} \sum_{j=0}^{\gamma_r - 2} {w_{t_r} \choose j} q^j(1-q)^{w_{t_r} - j}.\tag{98}\] Note that if \(\gamma_r = 1\) for some \(r \in [\ell]\), then we necessarily have \(s_r = 0\), and the corresponding “empty product” \(\prod_{t_r \in A_r} (\cdot)\) in 98 is interpreted as equaling 1 (i.e., that \(r\) value is effectively excluded). See also Footnote 3.

Lower Bounding \(\Pr(L_{\mathbf{A}}^+ \mid L_{\mathbf{A}}^-)\). As in the single-threshold setting, the conditioning on \(L_{\mathbf{A}}^-\) could lead to items no longer being defective independently, which complicates the analysis. A similar approach can be adopted here, except that we need to avoid overlaps from all sub-matrices indexed by \(r' \in [\ell]\), rather than only the \(r\) value matching the test under consideration. Thus, when considering a test \(t_r \in A_r^c\), we only consider the items that appear in none of the tests indexed by \(A_{r'}\) across every \(r' \in [\ell]\), where \(\mathbf{A} = (A_1,\dotsc,A_{\ell})\). We denote the number of such items as \(z_{t_r, \mathbf{A}}\).

In the single-threshold case, we lower bounded \(z_{t_r, \mathbf{A}}\) in a later part of the analysis, but here we do so immediately to ensure that each \(r \in [\ell]\) can be handled separately: We use Assumption 2 to obtain \(z_{t_r, \mathbf{A}} \ge z_{t_r} := w_{t_r} - c(d_{\max} - 1)\) with \(d_{\max} = \max_i \sum_{r'} d_{i,r'}\) denoting the maximum total degree. We assume for convenience that \(z_{t_r}\) is an integer; otherwise, rounding down suffices.

With the above modifications, we are now in a position to follow similar steps as the single-threshold case (i.e., argue the events are increasing, apply FKG, and substitute in the binomial probability), to obtain \[\begin{align} \tag{99} \Pr(L_{\mathbf{A}}^+ \mid L_{\mathbf{A}}^-) &\geq \prod_{r \in [\ell]} \prod_{t_r \in A_r^c} \left(1 - \sum_{j=0}^{\gamma_r - 1} {z_{t_r,\mathbf{A}} \choose j}q^j(1-q)^{z_{t_r,\mathbf{A}} - j}\right) \\ &\geq \prod_{r \in [\ell]} \prod_{t_r \in A_r^c} \left(1 - \sum_{j=0}^{\gamma_r - 1} {z_{t_r} \choose j}q^j(1-q)^{z_{t_r} - j}\right), \tag{100} \end{align}\] where the second step follows because the bracketed term is a binomial upper tail probability, and can only decrease when we reduce the first integer binomial parameter.

Combining Terms. Combining 98 and 100 gives \[\begin{align} \Pr(L_{\mathbf{A}}^- \cap L_{\mathbf{A}}^+) &\geq \left[\prod_{r \in [\ell]} \prod_{t_r \in A_r} \sum_{j=0}^{\gamma_r - 2} {w_{t_r} \choose j} q^j(1-q)^{w_{t_r} - j}\right] \nonumber \\ \tag{101}& \qquad \times \left[\prod_{r \in [\ell]} \prod_{t_r \in A_r^c} \left(1 - \sum_{j=0}^{\gamma_r - 1} {z_{t_r} \choose j}q^j(1-q)^{z_{t_r} - j}\right)\right] \\ &= \prod_{r \in [\ell]} \Bigg\{\Bigg[\prod_{t_r \in A_r} \sum_{j=0}^{\gamma_r - 2} {w_{t_r} \choose j} q^j(1-q)^{w_{t_r} - j}\Bigg] \nonumber\\ \tag{102} &\times \Bigg[\prod_{t_r \in A_r^c} \Bigg(1 - \sum_{j=0}^{\gamma_r - 1} {z_{t_r} \choose j}q^j(1-q)^{z_{t_r} - j}\Bigg)\Bigg]\Bigg\}. \end{align}\]

Summing Over \(\mathbf{A} \in \mathcal{A}_{\mathbf{s},i}\). Summing over all \(\mathbf{A} =(A_1,\dots, A_\ell) \in \mathcal{A}_{\mathbf{s},i}\) and using the above lower bound on \(\Pr(L_{\mathbf{A}}^- \cap L_{\mathbf{A}}^+)\), we obtain \[\begin{align} \Pr(L_{\mathbf{s},i}) &\geq \sum_{\mathbf{A} \in \mathcal{A}_{\mathbf{s},i}} \Bigg\{\prod_{r \in [\ell]} \Bigg\{\Bigg[\prod_{t_r \in A_r} \sum_{j=0}^{\gamma_r - 2} {w_{t_r} \choose j} q^j(1-q)^{w_{t_r} - j}\Bigg] \\ &\times \Bigg[\prod_{t_r \in A_r^c} \Bigg(1 - \sum_{j=0}^{\gamma_r - 1} {z_{t_r} \choose j}q^j(1-q)^{z_{t_r} - j}\Bigg)\Bigg]\Bigg\}\Bigg\}. \end{align}\] To simplify this, note that since \(\mathcal{A}_{\mathbf{s},i} = \mathcal{A}_{s_1,i} \times \cdots \times \mathcal{A}_{s_\ell, i}\), the sum \(\sum_{\mathbf{A} \in \mathcal{A}_{\mathbf{s},i}}\) can be equivalently written as \(\sum_{A_1 \in \mathcal{A}_{s_1,i}}\cdots \sum_{A_\ell \in \mathcal{A}_{s_\ell, i}}\). Substituting this in and swapping the order of the summations and product (which is justified since the \(r\)-th term inside the product \(\prod_{r \in [\ell]}\) depends only on the \(r\)-th coordinate of \(\mathbf{A}\)), we thus obtain \[\begin{align} \Pr(L_{\mathbf{s},i}) &\geq \prod_{r \in [\ell]} \Bigg\{ \sum_{A_r \in \mathcal{A}_{s_r,i}} \Bigg\{\Bigg[\prod_{t_r \in A_r} \sum_{j=0}^{\gamma_r - 2} {w_{t_r} \choose j} q^j(1-q)^{w_{t_r} - j}\Bigg] \nonumber \\ \label{eq:Pr95L95bfs95i95rearranged}& \times \Bigg[\prod_{t_r \in A_r^c} \Bigg(1 - \sum_{j=0}^{\gamma_r - 1} {z_{t_r} \choose j}q^j(1-q)^{z_{t_r} - j}\Bigg)\Bigg]\Bigg\}\Bigg\}. \end{align}\tag{103}\] Observe that the terms inside the product correspond exactly to those in the lower bound on \(\Pr(L_{s,i})\) given in 54 , with \(s\) renamed to \(s_r\) (alongside the other relevant quantities \(\gamma, A, \mathcal{A}_{s,i}, z_{t,A}, d_i, t, w_t, z_t\) also being renamed). Thus, we can directly use the final lower bound on \(\Pr(L_{s,i})\) given in 60 to lower bound 103 by \[\begin{align} \Pr(L_{\mathbf{s},i}) &\geq \prod_{r \in [\ell]} \Bigg\{ {d_{i,r} \choose s_r} \Bigg[\prod_{t_r \in [d_{i,r}]} \sum_{j=0}^{\gamma_r - 2} {w_{t_r}\choose j}q^j(1-q)^{w_{t_r} - j}\Bigg]^{\frac{s_r}{d_{i,r}}} \nonumber \\ \label{eq:Pr95bfs95i95lb95final} &\times \Bigg[\prod_{t_r \in [d_{i,r}]}\Bigg(1 - \sum_{j=0}^{\gamma_r -1}{z_{t_r}\choose j}q^j(1-q)^{z_{t_r} - j} \Bigg)\Bigg]^{\frac{d_{i,r}-s_r}{d_{i,r}}}\Bigg\}, \end{align}\tag{104}\] where we recall that \(z_{t_r} = w_{t_r} - c(d_{\max} - 1)\).

7.3.3 Step 3: Lower Bounding \(\Pr(D_{i})\)↩︎

Given the lower bound on \(\Pr(L_{\mathbf{s},i})\) in 104 , we proceed to lower bound \(\Pr(D_{i})\) in a similar manner as the single-threshold case. In particular, we use the relationship between the \(D_i\) and \(\{L_{\mathbf{s},i}\}_{\mathbf{s} \in \mathbf{S}_i}\) mentioned in Section 7.3.1 to lower bound \(\Pr(D_i)\) by \[\begin{align} \Pr(D_i) &\geq \sum_{\mathbf{s} \in \mathcal{S}_i}\Bigg\{\prod_{r \in [\ell]} \Bigg\{ {d_{i,r} \choose s_r} \Bigg[\prod_{t_r \in [d_{i,r}]} \sum_{j=0}^{\gamma_r - 2} {w_{t_r}\choose j}q^j(1-q)^{w_{t_r} - j}\Bigg]^{\frac{s_r}{d_{i,r}}} \nonumber \\ \label{eq:Pr95Di95selectable95init} &\times \Bigg[\prod_{t_r \in [d_{i,r}]}\Bigg(1 - \sum_{j=0}^{\gamma_r -1}{z_{t_r}\choose j}q^j(1-q)^{z_{t_r} - j} \Bigg)\Bigg]^{\frac{d_{i,r}-s_r}{d_{i,r}}}\Bigg\} \Bigg\}. \end{align}\tag{105}\] Recalling that \(\mathcal{S}_i = \{0,\dots, d_{i,1}\}\times \cdots \times \{0,\dots, d_{i,\ell}\}\), we can write \(\sum_{\mathbf{s} \in \mathcal{S}_i}\) as \(\sum_{s_1 \in \{0,\dots, d_{i,1}\}} \cdots \sum_{s_\ell \in \{0,\dots, d_{i,\ell}\}}\). By similar reasoning as the previous step, we can swap the order of the summations and the product to obtain \[\begin{align} \Pr(D_i) &\geq \prod_{r \in [\ell]} \Bigg\{ \sum_{s_r = 0}^{d_{i,r}} \Bigg\{{d_{i,r}\choose s_r} \Bigg[\prod_{t_r \in [d_{i,r}]} \sum_{j=0}^{\gamma_r - 2} {w_{t_r}\choose j}q^j(1-q)^{w_{t_r} - j}\Bigg]^{\frac{s_r}{d_{i,r}}} \nonumber \\ \tag{106}&\times \Bigg[\prod_{t_r \in [d_{i,r}]}\Bigg(1 - \sum_{j=0}^{\gamma_r -1}{z_{t_r}\choose j}q^j(1-q)^{z_{t_r} - j} \Bigg)\Bigg]^{\frac{d_{i,r}-s_r}{d_{i,r}}}\Bigg\} \Bigg\} \\ &= \prod_{r \in [\ell]}\Bigg\{ \Bigg[\Bigg( \prod_{t_r \in [d_{i,r}]}\sum_{j=0}^{\gamma_r-2}{w_{t_r} \choose j}q^j (1-q)^{w_{t_r} - j}\Bigg)^{\frac{1}{d_{i,r}}} \nonumber \\ \tag{107} &+ \Bigg(\prod_{t_r \in [d_{i,r}]}\Bigg(1 - \sum_{j=0}^{\gamma_r - 1}{z_{t_r} \choose j} q^j(1 - q)^{z_{t_r} - j}\Bigg)\Bigg)^{\frac{1}{d_{i,r}}}\Bigg]^{d_{i,r}} \Bigg\}, \end{align}\] with 107 following from the binomial formula. To further lower bound this, we can lower bound both sums in 107 analogously to 63 –64 for each \(r \in [\ell]\), which gives \[\begin{align} \Pr(D_i) &\geq \prod_{r \in [\ell]} \Bigg\{\Bigg[\sum_{j=0}^{\gamma_r - 2}{w_{r}^{\max} \choose j}q^j (1-q)^{w_{r}^{\max}-j} + 1 - \sum_{j=0}^{\gamma_r-1} {z_{r}^{\min} \choose j} q^j (1-q)^{z_{r}^{\min} - j}\Bigg]^{d_{i,r}}\Bigg\} \\ &\geq \prod_{r \in [\ell]} \Bigg\{\Bigg[\sum_{j=0}^{\gamma_r- 2}{w_{r}^{\max} \choose j}q^j (1-q)^{w_{r}^{\max}-j} + 1 - \sum_{j=0}^{\gamma_r-1} {z_{r}^{\min} \choose j} q^j (1-q)^{z_{r}^{\min} - j}\Bigg]^{d_{r}^{\max}}\Bigg\}, \label{eq:bound95by95max95d} \end{align}\tag{108}\] where \(d_{r}^{\max} := \max_{i} d_{i,r}\) (and we later similarly use \(d_{r}^{\min} := \min_{i} d_{i,r}\)), \(w_{r}^{\max} \mathrel{\vcenter{:}}= \max_{{t_r} \in \mathcal{T}_r} w_{t_r}\) (and similarly \(w_{r}^{\min}\)), and \(z_{r}^{\min} \mathrel{\vcenter{:}}= \min_{t_r \in \mathcal{T}_r} z_{t_r} = w_{r}^{\min} - c(d_{\max} - 1)\), recalling that \(\mathcal{T}_r \subseteq [T]\) is the set of test indices with threshold \(\gamma_r\). To obtain our final lower bound on \(\Pr(D_i)\), we upper bound \(d_{\max,r}\) in terms of \(T\). Note that 108 uses that the argument to \([\cdot]\) is at most one, since it is a lower bound on a binomial probability.

An analogous double counting argument to that in the single-threshold case reveals that \(\sum_{i=1}^nd_{i,r} = \sum_{t_r \in \mathcal{T}_r}w_{t_r}\) (recall that \(d_{i,r}\) is the number of threshold-\(\gamma_r\) tests \(i\) is included in), which implies that \(nd_{r}^{\min} \leq \lvert \mathcal{T}_r\rvert (w_{r}^{\max}+1)\). Assumption 3 also implies that \(nd_{r}^{\min} \geq \frac{n d_{r}^{\max}}{\zeta_r}\), which combined with the aforementioned double counting argument, implies that \(d_{r}^{\max} \leq \frac{\zeta_r \lvert \mathcal{T}_r \rvert (w_{r}^{\max}+1)}{n}\) for each \(r \in [\ell]\). Recalling that \(\alpha_r \in [0,1]\) is defined such that \(\lvert \mathcal{T}_r \rvert = \alpha_r T\) for each \(r \in [\ell]\), and using the above bound on \(d_{r}^{\max}\), we thus have that \(\Pr(D_i)\) is lower bounded by \[\begin{align} \Pr(D_i) &\geq \prod_{r \in [\ell]} \Bigg\{\Bigg[\sum_{j=0}^{\gamma_r - 2}{w_{r}^{\max} \choose j}q^j (1-q)^{w_{r}^{\max}-j} \nonumber \\ \label{eq:Pr95Di95lb95selectable95final} &+ 1 - \sum_{j=0}^{\gamma_r-1} {z_{r}^{\min} \choose j} q^j (1-q)^{z_{r}^{\min} - j}\Bigg]^{\frac{\zeta_r \alpha_r T (w_{r}^{\max}+1)}{n}}\Bigg\}. \end{align}\tag{109}\]

7.3.4 Lower Bounding the Number of Masked Items, i.i.d. Prior↩︎

Given the lower bound on \(\Pr(D_i)\) derived above, we can follow the same steps as in Section 7.2.4 to obtain a high probability lower bound on the number of masked items. Specifically, we can use the lower bound on \(\lvert \mathcal{I}\rvert\) and the fact that its masking events are mutually independent (Lemma 8), alongside 109 , to argue that \[\label{eq:stochastic95dom95selectable} {\rm Bin}\left(n^{1-3\xi}, \prod_{r \in [\ell]}\Xi_r^{\frac{\zeta_r \alpha_r T (w_{r}^{\max}+1)}{n}}\right) = {\rm Bin} \left(n^{1-3\xi}, \exp\left(\frac{T}{n}\sum_{r \in [\ell]}\zeta_r \alpha_r (w_{r}^{\max}+1)\log (\Xi_r)\right)\right) \preceq_{\rm st}M,\tag{110}\] where \(\Xi_r\) is the term inside the exponent in 109 for each \(r \in [\ell]\). The expected value of the binomial random variable is then \[\label{eq:ev95binom95selectable} n^{1-3\xi}\exp\left(\frac{T}{n}\sum_{r \in [\ell]}\zeta_r \alpha_r (w_{r}^{\max}+1)\log (\Xi_r)\right),\tag{111}\] which is at least \(n^{2\xi}\) whenever \[\begin{align} \label{eq:selectable95T95init} T& \leq \frac{(1-5\xi)n \log n}{\displaystyle-\sum_{r \in [\ell]}\zeta_r \alpha_r (w_{r}^{\max}+1) \log (\Xi_r)} \\ &= \frac{(1-5\xi)n \log n}{\displaystyle-\sum_{r \in [\ell]} \zeta_r \alpha_r (w_{r}^{\max}+1) \log \Bigg(\sum_{j=0}^{\gamma_r - 2}{w_{r}^{\max} \choose j}q^j (1-q)^{w_{r}^{\max}-j} + 1 - \sum_{j=0}^{\gamma_r-1} {z_{r}^{\min} \choose j} q^j (1-q)^{z_{r}^{\min} - j}\Bigg)}. \end{align}\tag{112}\] Under Assumption 2, \(z_{r}^{\min}\) satisfies \(z_{r} = w_{r}(1-o(1))\) for each \(r \in [\ell]\).⁶ Additionally, Assumption 3 gives that \(\zeta_r = 1+o(1)\) and \([w_{r}^{\min}, w_{r}^{\max}+1] = [\Delta_r (n/k)(1-o(1)), \Delta_r(n/k)(1+o(1))]\) for each \(r \in [\ell]\). Using these and the Poisson approximation to the binomial (Lemma 5), the condition on \(T\) can be written as \[\begin{align} \tag{113} T &\leq \frac{n \log n}{\displaystyle-\sum_{r \in [\ell]}\alpha_r \Delta_r(n/k) \log\left(\sum_{j=0}^{\gamma_r -2} \frac{\Delta_r^j e^{-\Delta_r}}{j!} + 1 - \sum_{j=0}^{\gamma_r - 1}\frac{\Delta_r^j e^{-\Delta_r}}{j!}\right)}(1-5\xi)(1-o(1)) \\ \tag{114} &= \frac{k \log k}{\displaystyle-\sum_{r \in [\ell]}\alpha_r \Delta_r \log \left(1 - \frac{\Delta_r^{\gamma_r - 1}e^{-\Delta_r}}{(\gamma_r - 1)!}\right)}(1-\varepsilon), \end{align}\] where in 113 we have used \(n = k^{\frac{1}{1-\xi}}\) and introduced \(\varepsilon > 0\) that is arbitrarily small as a function of arbitrarily small \(\xi > 0\) (and the \(1-o(1)\) term). Taking the minimum over \((\Delta_1, \dots, \Delta_\ell) \in \mathbb{R}_+^\ell\), it follows that 111 is at least \(n^{2\xi}\) for all \((\Delta_1,\dots, \Delta_\ell)\) as long as \[\label{eq:selectable95T95optimised} T \leq \min_{(\Delta_1,\dots \Delta_\ell) \in \mathbb{R}_+^\ell} \frac{k \log k}{\displaystyle-\sum_{r \in [\ell]}\alpha_r \Delta_r \log \left(1 - \frac{\Delta_r^{\gamma_r - 1}e^{-\Delta_r}}{(\gamma_r - 1)!}\right)}(1-\varepsilon).\tag{115}\] To conclude this step, we can proceed in the same way as in the end of Section 7.2.4 to show that the event \(\mathcal{E} = \{M_0 \leq \frac{1}{4}n^{2\xi}\} \cup \{M_1 = 0\}\) (i.e., the event that there are at most \(\frac{1}{4}n^{2\xi}\) masked non-defectives or no masked defectives) holds with probability \(\exp(-\Omega(n^\xi))\).

7.3.5 Wrapping Up↩︎

Finally, as discussed in Section 7.3.1, Steps 5-7 can be applied in the exact same way as in the single-threshold case, with their analyses remaining (almost)⁷ entirely unchanged (see Sections 7.2.5-7.2.7 for these analyses). Since these steps are unchanged, we do not repeat the details, and only note that these steps jointly show that \(\Pr(\hat{S} = S) = o(1)\) under the combinatorial prior for any decoder \(\hat{S}\), sparsity parameter \(\theta\), and test design \(\mathbf{X}\) satisfying Assumptions 2-3, as long as 115 holds. Thus, we can conclude that in order for \(\Pr(\hat{S} \neq S) \nrightarrow 1\), it is necessary that \[\label{eq:selectable95T95final} T \geq \min_{(\Delta_1,\dots \Delta_\ell) \in \mathbb{R}_+^\ell} \frac{k \log k}{\displaystyle-\sum_{r \in [\ell]}\alpha_r \Delta_r \log \left(1 - \frac{\Delta_r^{\gamma_r - 1}e^{-\Delta_r}}{(\gamma_r - 1)!}\right)}(1-o(1)).\tag{116}\] This completes the proof of Theorem 6.

7.4 Proof of Lemma 1 (Maximization of \(f\))↩︎

Throughout the proof, we denote \[A(\Delta,\gamma)=\dfrac{\Delta^{\gamma-1}}{\Gamma(\gamma)}e^{-\Delta}, \quad \text{ and thus } \quad h(\Delta,\gamma) = -\Delta \log\big( 1-A(\Delta,\gamma) \big), \label{eq:def95A}\tag{117}\] where \(\Gamma(\cdot)\) is the gamma function. When \(\gamma\) is integer-valued (as is the case in Lemma 1) we have the simplification \(\Gamma(\gamma) = (\gamma-1)!\), but later in the proof we will consider general real-valued \(\gamma > 0\) in 117 in order to permit differentiation with respect to \(\gamma\).

By the definitions \(\Delta^*_{r} \mathrel{\vcenter{:}}= \arg\max_{\Delta> 0} h(\Delta,\gamma_r)\) and \(r^* \mathrel{\vcenter{:}}= \arg\max_{r \in [\ell]} \gamma_r\), there exist choices \(\boldsymbol{\alpha}^*\) and \(\mathbf{\Delta}^*\) such that \(f(\boldsymbol{\alpha}^*,\mathbf{\Delta}^*,\boldsymbol{\gamma})= h(\Delta^*_{r^*},\gamma_{r^*})\). To establish Lemma 1, it suffices to show that \[f(\boldsymbol{\alpha},\boldsymbol{\Delta},\boldsymbol{\gamma})\le h(\Delta^*_{r^*},\gamma_{r^*})\quad\forall \boldsymbol{\alpha},\boldsymbol{\Delta}.\] Consider an arbitrary tuple \((\boldsymbol{\alpha},\boldsymbol{\Delta},\boldsymbol{\gamma})\). Denoting \(r_0=\arg\max_{r\in[\ell]}h(\Delta_r,\gamma_r)\), we have \[f(\boldsymbol{\alpha},\boldsymbol{\Delta},\boldsymbol{\gamma})\le h(\Delta_{r_0},\gamma_{r_0}),\] since \(f\) is an average of \(h(\Delta_r,\gamma_r)\) values and is thus upper bounded by the maximum. We will establish that \[h(\Delta_{r_0},\gamma_{r_0})\le h(\Delta_{r_0}^*,\gamma_{r_0})\le h(\Delta_{r^*}^*,\gamma_{r^*}).\] The first inequality follows directly from the definition of \(\Delta_r^*\). We proceed to prove the second inequality, starting with the following lemma limiting the range of \(\Delta_{r}^*\) for \(\gamma_r \ge 2\), and similarly for non-integer thresholds exceeding 2. (The case \(\gamma_r = 1\) was already handled in standard GT [20], and will be treated separately later.)

Next, we state another lemma stating the conditions under which \(h(\Delta^*(\gamma),\gamma)\) is increasing in \(\gamma\), again treating \(\gamma\) as a general real number (not necessarily an integer).

Now, note that due to Lemma 9, we have \(\Delta^*>\gamma-\frac{1}{3}\), and hence \[\log \Delta^*>\log\Bigl(\gamma-\frac{1}{3}\Bigr) \ge \log(\gamma)-\dfrac{1}{2\gamma}\ge \Psi(\gamma)\quad \forall \gamma\ge 2,\] where the middle inequality uses \(\log(x-1/3) \ge \log(x) - 1/(2x)\) for \(x \ge 2\) (which can be verified analytically or graphically), and the last inequality can be found in [43]. Thus, by ?? , we have \[\frac{d}{d\gamma}\, h(\Delta^*,\gamma)>0\quad\text{for all }\gamma\ge 2,\] which establishes that these values are monotonically increasing for \(\gamma \ge 2\). Moreover \(h(\Delta^*,\gamma)\) is strictly higher for \(\gamma = 2\) than for \(\gamma = 1\): For \(\gamma=1\), its value is \((\log 2)^2<0.5\) [20], whereas for \(\gamma = 2\) its value is at least \(h(3/2,2) = -\frac{3}{2}\log\big(1-\frac{3}{2} e^{-3/2}\big) >0.6\). Thus, \(\gamma = 1\) can never give the highest value as long as there is a higher integer-valued threshold. Since \(r^*\) is defined such that \(\gamma_{r*}\) is the highest threshold, it follows that \(h(\Delta_{r_0}^*,\gamma_{r_0})\le h(\Delta_{r^*}^*,\gamma_{r^*})\), which completes the proof.

7.5 Proof of Lemma 2 (The Large-\(\gamma\) Limit)↩︎

Let \[A_\gamma(\Delta)\mathrel{\vcenter{:}}=\frac{\Delta^{\gamma-1}}{(\gamma-1)!}e^{-\Delta},\qquad G_\gamma(\Delta)\mathrel{\vcenter{:}}= -\Delta\log\bigl(1-A_\gamma(\Delta)\bigr),\qquad \Delta\in[\gamma-1/3,\gamma],\] and write \(\Delta=\gamma-\varepsilon\) with \(\varepsilon\in[0,1/3]\). By Stirling’s formula, we have \[(\gamma-1)! = \sqrt{2\pi(\gamma-1)}\,(\gamma-1)^{\gamma-1}e^{-(\gamma-1)}\bigl(1+o(1)\bigr),\] and hence \[A_\gamma(\gamma-\varepsilon) =\frac{(\gamma-\varepsilon)^{\gamma-1}e^{-(\gamma-\varepsilon)}}{\sqrt{2\pi(\gamma-1)}(\gamma-1)^{\gamma-1}e^{-(\gamma-1)}}\bigl(1+o(1)\bigr) =\frac{e^{-(1-\varepsilon)}}{\sqrt{2\pi(\gamma-1)}}\Bigl(1+\frac{1-\varepsilon}{\gamma-1}\Bigr)^{\gamma-1}\bigl(1+o(1)\bigr). \label{eq:minus95eps}\tag{119}\] Since \(\varepsilon\in[0,1/3]\) is bounded, we have uniformly in this range of \(\varepsilon\) that \[\Bigl(1+\frac{1-\varepsilon}{\gamma-1}\Bigr)^{\gamma-1} =\exp\Bigl((\gamma-1)\log\Bigl(1+\frac{1-\varepsilon}{\gamma-1}\Bigr)\Bigr) =\exp\bigl((1-\varepsilon)+o(1)\bigr)=e^{1-\varepsilon}\bigl(1+o(1)\bigr).\] Hence, the exponential factors cancel in 119 , giving \[\sup_{\Delta\in[\gamma-1/3,\gamma]}\left|A_\gamma(\Delta)-\frac{1}{\sqrt{2\pi\gamma}}\right|=o\left(\frac{1}{\sqrt{\gamma}}\right),\] and in particular \[\sup_{\Delta\in[\gamma-1/3,\gamma]}A_\gamma(\Delta)=O(\gamma^{-1/2}).\] Using \(\,-\log(1-u)=u+O(u^2)\) as \(u\to0\), we obtain uniformly for \(\Delta\in[\gamma-1/3,\gamma]\) that \[G_\gamma(\Delta)=\Delta\Bigl(A_\gamma(\Delta)+O(A_\gamma(\Delta)^2)\Bigr)=\Delta\cdot A_\gamma(\Delta)+O\Bigl(\Delta\cdot A_\gamma(\Delta)^2\Bigr).\] Now, \(\Delta\in[\gamma-1/3,\gamma]\) implies \(\Delta=\gamma-O(1)\), while \(A_\gamma(\Delta)=O(\gamma^{-1/2})\), so \[\Delta \cdot A_\gamma(\Delta)^2 = O(\gamma\cdot \gamma^{-1})=O(1), \quad\text{and}\quad \Delta\cdot A_\gamma(\Delta)=\bigl(\gamma-O(1)\bigr)\Bigl(\frac{1}{\sqrt{2\pi\gamma}}+o(\gamma^{-1/2})\Bigr) =\sqrt{\frac{\gamma}{2\pi}}\bigl(1+o(1)\bigr),\] uniformly over \(\Delta\in[\gamma-1/3,\gamma]\). Multiplying by \(\sqrt{2\pi/\gamma}\) gives \[\sup_{\Delta\in[\gamma-1/3,\gamma]}\left|\,G_\gamma(\Delta)\sqrt{\frac{2\pi}{\gamma}}-1\,\right| \to 0,\] which establishes the first part of the lemma. The second part follows directly from Lemma 9.

8 Verification of Assumptions for the NCC Design↩︎

In this appendix, we verify that Assumptions 1 and 2 hold with probability \(1-o(1)\) under the NCC design (Definition 2) with \(L = \frac{\nu T}{k}\) for any fixed parameter \(\nu > 0\) and any number of tests satisfying \(T = \Theta(k \log n)\). For convenience, we write \(T = C k \log n\) with \(C = \Theta(1)\).

Assumption 1 can be verified (almost) directly from the findings of [19]:

• The first step in [19] is precisely to establish that each item is placed in \(L - O(1)\) distinct tests. Since \(L \to \infty\), this is a strictly stronger statement than our requirement of \(L(1-o(1))\).

• [19] states that with probability \(1-o(1)\), all row weights behave as \(\frac{\nu n}{k} + O\big( \sqrt{\frac{\nu n}{k}} \log n \big)\) when repeated placements (i.e., “multi-edges”) are counted. When \(\nu = \Theta(1)\) and \(k = \Theta(n^{\theta})\), this simplifies to the desired behavior \(\frac{\nu n}{k}(1+o(1))\).

  It remains to establish that removing repeated placements changes each row weight by only \(o(n/k)\). For a fixed test, the expected number of items placed in that test at least twice is \(O(n/k^2)\), since for each item this probability is at most \(\binom{L}{2}/T^2=O(k^{-2})\). A Chernoff bound, together with a union bound over all tests and the \(O(1)\) bound on the total number of repeated placements per item from [19], then yields a uniform \(o(n/k)\) bound on the number of repeated placements per test. Since this argument is largely similar to 120 –125 below, we omit the remaining details.

In the following, we verify Assumption 2. Fix two distinct tests \(t_1,t_2\in[T]\), and let \(V_{t_1,t_2}\) denote the number of items appearing in both tests. For a given item, the probability of appearing in both specified tests is at most \[\Pr(i \text{ in both } t_1 \text{ and } t_2) \le \left(\frac{L}{T}\right)^2 = \frac{\nu^2}{k^2}. \label{eq:both95prob}\tag{120}\] Since items are placed independently, we have the stochastic domination \[V_{t_1,t_2} \preceq_{\rm st}\mathrm{Bin}\left(n,\frac{\nu^2}{k^2}\right). \label{eq:overlap95domination}\tag{121}\] The mean of the dominating binomial variable is \[\mu_V = \nu^2\frac{n}{k^2} = \Theta(n^{1-2\theta}). \label{eq:overlap95mean}\tag{122}\] We now split into two regimes.

The case \(\theta < 1/2\). Here \(\mu_V=n^{\Omega(1)}\). By the Chernoff bound, for any fixed pair \((t_1,t_2)\), we have \[\Pr\left( V_{t_1,t_2} \ge 2\mu_V \right) \le \exp(-\Omega(\mu_V)).\] Since there are at most \(T^2=O(k^2\log^2 n)\) pairs of tests, and \(\mu_V=n^{\Omega(1)}\), a union bound gives \[\max_{t_1\ne t_2} V_{t_1,t_2} = O\left(\frac{n}{k^2}\right) = O(n^{1-2\theta}) \label{eq:c95sparse}\tag{123}\] with probability \(1-o(1)\). Thus, Assumption 2 holds with a polynomial “margin”, in the sense that \(n^{1-2\theta}\) is smaller than \(\frac{n}{k \log n}\) by a factor of \(O\big(\frac{\log n}{n^{\theta}}\big)\).

The case \(\theta \ge 1/2\). Here \(\mu_V=O(1)\). Fix \(A > 0\) and let \[a_n = \frac{A\,\log n}{\log\log n}\] Using the standard binomial tail bound \[\Pr(V \ge a) \le \left(\frac{e \mathbb{E}[V]}{a}\right)^{a}, \label{eq:bin95tail95large}\tag{124}\] we obtain for sufficiently large \(A\) that \[\Pr( V_{t_1,t_2}\ge a_n ) \le O(n^{-3}).\] Since \(T^2=O(k^2\log^2 n)\le O(n^2\log^2 n)\), a union bound yields with probability \(1-o(1)\) that \[\max_{t_1\ne t_2} V_{t_1,t_2} = O\left(\frac{\log n}{\log\log n}\right). \label{eq:c95dense}\tag{125}\] This is again significantly smaller than the required \(o\big( \frac{n}{k \log n} \big)\) in Assumption 2; this time the bound is sub-logarithmic in \(n\) when even a (small enough) polynomial upper bound would have sufficed.

References↩︎

---

1. The authors are with the Department of Computer Science, National University of Singapore (NUS). J. Scarlett is also with the Department of Mathematics and Institute for Data Science at NUS. This work is supported by the National University of Singapore under the Presidential Young Professorship grant scheme.↩︎

2. The choice of rounding here is inconsequential, so is omitted.↩︎

3. We define the number of items in a test as \(w_t + 1\) purely for notational convenience in the proof of Theorem 5, as it avoids the extensive inclusion of \(-1\) terms if \(w_t\) were the weight.↩︎

4. If \(\gamma = 1\) then the first term should be omitted in order to avoid taking the logarithm of zero. The subsequent equations from 60 onward still hold for \(\gamma = 1\) by following the analysis with the first term omitted (or more simply relying on the standard GT analysis in [20]). ↩︎

5. While this is stated in [20] for the classical group testing problem, the exact same argument applies for our setting, so we omit the details.↩︎

6. Assumption 3 ensures that \(d_{i,r} = \Theta(\log n)\) for every \((i,r)\), and since the number of thresholds \(\ell\) is constant, this implies that the maximum total degree \(d_{\max}\) in the definition of \(z_{r}\) also scales as \(\Theta(\log n)\).↩︎

7. The only difference between steps 5-7 here and steps 5-7 in the single-threshold setting is that the arguments surrounding 90 –92 need to be repeated for each \(r \in [\ell]\), so we can establish the required concentration of \(W_{t_r}'\) for each \(t_{r} \in \mathcal{T}_r\) and \(r \in [\ell]\) via a union bound (under Assumption 3). Since this straightforward change is the only one across the three steps, we omit the details.↩︎

8. This is a simplified form of their lower bound that replaces \(x^2 + x/3 + a_*\) by \(x^2\) in their notation (since \(x,a_* > 0\)). Their constraint \(x \ge 1\) translates to our \(\gamma \ge 2\) via the relation \(x = \gamma - 1\).↩︎