key: cord-0214340-10xu7eoq
authors: Gabrys, Ryan; Pattabiraman, Srilakshmi; Rana, Vishal; Ribeiro, Joao; Cheraghchi, Mahdi; Guruswami, Venkatesan; Milenkovic, Olgica
title: AC-DC: Amplification Curve Diagnostics for Covid-19 Group Testing
date: 2020-11-10
journal: nan
DOI: nan
sha: bdea517b20eec997a4251dcff0a63bad1b5f8301
doc_id: 214340
cord_uid: 10xu7eoq

The first part of the paper presents a review of the gold-standard testing protocol for Covid-19, real-time, reverse transcriptase PCR, and its properties and associated measurement data such as amplification curves that can guide the development of appropriate and accurate adaptive group testing protocols. The second part of the paper is concerned with examining various off-the-shelf group testing methods for Covid-19 and identifying their strengths and weaknesses for the application at hand. The third part of the paper contains a collection of new analytical results for adaptive semiquantitative group testing with probabilistic and combinatorial priors, including performance bounds, algorithmic solutions, and noisy testing protocols. The probabilistic setting is of special importance as it is designed to be simple to implement by nonexperts and handle heavy hitters. The worst-case paradigm extends and improves upon prior work on semiquantitative group testing with and without specialized PCR noise models.

I N less than ten months since the first case reported in the Hubei province of China, Covid-19 has rapidly spread across all continents except Antarctica [1] . The disease has caused more deaths than Ebola, SARS, and the seasonal Flu combined (reaching 1, 000, 000 mortalities in September 2020), disrupted the global economy to an extent not seen since the Great Depression and altered the lives of hundreds of millions of people across the globe [2] .

Many analyses associated with the Covid-19 pandemic have established that widespread population testing is key to effectively containing outbreaks of this and other infectious diseases. In May 2020, the United States was able to test around 150, 000 people per day (According to the Covid Tracking Project, this number has since increased to 750, 000 in August), while countries that have managed to keep the outbreak under control, such as Germany and South Korea, have performed millions of tests during the same stage of the spread of the disease. Although there is no general consensus on the exact number of individuals that need to be tested, most experts agree that the reported numbers are highly inadequate and should be at least an order of magnitude higher before the economy can be safely reopened to the pre-pandemic extent [3] . Some universities, such as Yale University, and the University of Illinois, currently have a biweekly test schedule in place for all individuals accessing school property [4] . This is believed to be a sufficiently large-scale testing protocol that allows the institution to safely operate.

To address the need for sustainable high-frequency population testing, a number of countries and states proposed and implemented group testing schemes in which genetic samples from different individuals are pooled together in a manner that incorporates thresholded real time reverse transcriptase polymerase chain reaction (RT-PCR) fluorescence signals into the testing scheme 1 .

Group testing (GT) is a combinatorial screening method introduced by Dorfman [6] for identifying small groups of soldiers infected by Syphilis. His scheme, known as single-pooling, consists of mixing blood samples from five soldiers at a time, and running one test for each pool. For positive test outcomes, the soldiers involved in the test are examined individually in a second round to determine who has the disease. For negative outcomes, all subjects involved are declared healthy and removed from future testing schedules. Given a relatively small number of infected individuals in a population, this scheme provides a significant reduction in the number of tests required when compared to individual testing [7] . The scheme proved ineffective for its original task as blood sample pooling dilutes the resulting sample to a point below the sensitivity of the tests used.

A number of recent reports suggest using Dorfman's or other mostly off-the-shelf GT schemes for Covid-19 testing [8] - [17] . Most of the proposed schemes do not incorporate relevant biological priors or exploit the highly specific measurement and noise properties of the RT-PCR method in their testing schemes. We argue this is a significant detriment, as in order to properly execute the effort and avoid dangerous failures, testing schemes should to be guided both by mathematical considerations as well as social, clinical, and genomic side information 2 . This suggests designing Covid-19 group testing schemes that carefully address the following issues: 1) Selection of adequate primers. As stated in the CDC SARS-CoV-2 testing guidelines [20] , only two primers are recommended for use in the USA for RT-PCR reactions, selected from the N open reading frame (ORF) of the SARS-CoV-2 genome. It is often hard to predict which regions will have small mutations and it is currently not known how fast the N regions and other primer regions chosen by various countries mutate and how these mutations affect the PCR protocol. To determine the influence of mutations one first needs to determine which regions will remain mostly unaffected by mutations, determine the melting temperatures of the primers [21] and their binding affinity to the mutated reference regions. For this purpose, the recent work [22] may be used to guide the primer selection process, while actually recorded mutated N primer regions may be used to estimate the failure rates of the individual PCR tests or model the errors in group PCR protocols due to mutations. These issues will be examined in Sections II and V. 2) Selection of (near-)optimal sample mixing strategies with priors. If not properly designed, GT schemes may lead to errors that are even more detrimental to the population than no tests at all. Since some individuals, such as health workers, may harbor multiple strains of the virus, and since clinical priors are often readily available (e.g., symptom charts, chest X-ray images) the sampling and mixing approaches should be carefully designed to include the right number and combinations of subjects in order to minimize test errors. This is a complicated issue that will be examined elsewhere. 3) Use of quantitative test outcomes. RT-PCR experiments provide significantly more information about the viral load or number of infected individuals within the group rather than just a simple binary answer, "no infected samples" or "at least one infected sample". Except for a handful of works proposing to use quantitative RT-PCR through Compressed Sensing (CS) [23] - [25] , most reported Covid-19 GT schemes assume binary test outcomes (among them the scheme used in Israel and described in [26] ). Furthermore, practically tested schemes operate in a nonadaptive setting, which is suboptimal and not justified for large-scale testing strategies which use a limited number of PCR machines. Another important issue is that heavy hitters (individuals with very high viral loads) can "mask" individuals with smaller loads which makes the use of quantitative information difficult [27] , [28] . This masking phenomena, as well as saturation effects present in RT-PCR outputs, can make CS approaches highly susceptible to errors. The focus of this work is to develop schemes that can address these issues in a simple, yet efficient manner. Consequently, our main results pertain to scalable, adaptive and semiquantitative testing methods that can efficiently handle heavy hitters and errors that are specific to RT-PCR systems. 4) Incorporation of social/contact network information. Due to the highly heterogeneous response of individuals to the infection, diverse infection rates across different geographic and communal regions, the best testing practices have to be guided by infection risk assessments and scores. Such "network-guided" schemes are currently known in the GT and CS literature, except for a recent work that uses community information to model correlations and reduce the number of tests required [29] . Instead, we propose to identify highly infected communities and their neighboring communities rather than all individuals in each infected community. In this case, GT is used jointly with other commonly employed mitigation strategies such as quarantine. "Heavily infected" community detection as well as heavy hitter problems arising in Covid-19 are discussed in Section IV. We argue that the availability of (semi)quantitative test outcomes and the use of adaptive strategies can greatly increase the efficiency and scalability of Covid-19 testing schemes. In that direction, we generalize the Semiquantitative Group Testing (SQGT) strategy [30] - [32] to an adaptive setting and devise simple probabilistic adaptive GT methods 3 and worst-case adaptive GT schemes that take the specific measurement data noise and quantization properties into account. The SQGT scheme assumes that one cannot tell the exact viral load or number of infected individuals in a pool but only an interval in which the load or number of defectives lies. The setting is a generalization of GT that includes more than two outcomes, or a quantized version of the adder channel/CS approach [35] , [36] . It also represents a generalization of the setting [37] in which only saturation effects are taken into account within the adder model. It is worth pointing out that this is also the first approach that uses actual RT-PCR features and also postulates rigorous models that allow for relating viral loads to actual fluorescence values and analyze the testing schemes rigorously. Other methods that will be reviewed in later sections either completely ignore the RT-PCR measurements or do not properly justify or analyze their proposed models.

For an illustration of the differences between various testing schemes (group testing, additive tests, additive tests with saturation, and general SGQT), the reader is referred to Figure 1 . For the worst case setting, in which we assume a known number of d defectives, but make no assumptions about how they are distributed, and where one can tell if zero defectives were present, or the number of defectives is nonzero and lies in one out of m consecutive intervals of length τ, the number of tests per defective roughly equals log pn{dq`log logpm`1q logpm`1q .

The savings in the number of tests as compared to the classical GT setting provided by the increased resolution of the levels is logpm`1q-fold, which even for 7 levels amounts to three-fold savings. Clearly, one has to be able to properly calibrate the RT-PCR readouts and determine adequate thresholds in order to take full advantage of the scheme. This issue will be addressed in Section II.

For the probabilistic setting, where each item is assumed to be independently defective with some probability, our main results include simple-to-implement algorithms for adaptive testing that involve two thresholds and two test stages, and are also capable of handling heavy hitters (i.e., individuals with high viral loads that may mask other individual's presence, provided these individuals are not too common.)

The remainder of the paper is organized as follows. Section II provides an overview of the PCR, RT-PCR and the Real Time (Quantitative) PCR techniques. The section also addresses key issues that impede the amplification efficiency of the methods currently used for Covid-19 testing and introduces several practical noise models. Section III describes various GT approaches and assesses their utility for Covid-19 testing. Sections IV and V describe the main original results. Section IV describes a probabilistic version of a SQGT model, simplified to account for two rounds of testing and two test thresholds only. This section also introduces test schemes that aim to identify highly virulent individuals, termed heavy hitters. Section V introduces a new worst-case adaptive SQGT technique that is near-optimal and describes a noise model termed the birth-death chain model. Section VI provides preliminary directions towards designing efficient community-aware testing strategies. Section VII reports the results obtained using the GISAID database [38] that explain the influence of mutations in the primer regions on the efficiency of the tests and therefore suggests that noise models previously considered in the literature that only account for errors in the PCR test are inadequate. Section VIII concludes the paper and discusses future work.

We start our exposition by describing the real-time reverse transcriptase (RT-PCR) testing mechanism. DNA has a double helix structure and both strands in the helix are composed of periodic sugar and phosphate groups to which one of four different bases is attached, namely A, T, C, and G. A sugar, phosphate, and base are jointly referred to as a nucleotide. As the sugar is asymmetric in terms of the placement of its carbon atoms with respect to the position of binding to the phosphates, the two strands of the DNA have two different directions: One runs from the 3' to 5' carbon end, while the other runs from the 5' to 3' carbon end. The two strands are held together through the stacking of bases and the hydrogen bonds that exist between them. The pairing rule is dictated by Watson-Crick (WC) complementarity asserting that only (or with overwhelming probability) the bases A and T and G and C bind to each other, respectively.

The Reverse-Transcriptase PCR (RT-PCR) technique is used to identify/amplify RNA strands. Since RNA is single-stranded and hence an unstable molecule, RT-PCR first converts the target RNA into its complementary double-stranded DNA (cDNA, as illustrated in Figure 2 ) and then performs amplification using the standard PCR technique. Note that RNA has three of the same building blocks as DNA, namely A, C, and G, but instead of T (encountered in DNA), RNA contains U (Uracil).

Conversion of RNA into cDNA is accomplished through the use of the reverse transcriptase (RT) enzyme that stitches together "free" nucleotides A, T, C, and G together, in the presence of primers that are complementary to a specific part of the target RNA sample (see Figure 4 2 ). Since RNA is inherently single-stranded, the primers have an affinity to attach to the complementary RNA regions, recruit the RT enzyme and thereby initiate synthesis. The process proceeds through two steps: In the first step, the first-strand cDNA is created using the single-stranded RNA as a template. In the second step, the second-strand cDNA is formed by using the first-strand cDNA as template. Consequently, the product cDNA represents an accurate replica of the original RNA content, converted to the DNA alphabet.

The test results are usually compared to a control as a means to assess the quality of the experiment. RT-PCR is used to detect RNA viruses, i.e., viruses whose genomic content is stored in RNA rather than DNA. SARS-Cov-2, the virus causing Covid-19, is an RNA virus, as is for example the HIV virus that causes AIDS. For viral detection, the first step of testing involves isolating genomic RNA by breaking the viral membrane, but this and other processes that lead to actual sample isolation will not be discussed in this short review. The Covid-19 detection and amplification process relies on standard RT-PCR methods and RT-PCR and its quantitative version described next.

The Polymerase Chain Reaction (PCR) is used to amplify specific segments of the DNA strands in order to enable a downstream analysis of the segments or to detect the presence of specific DNA content. The operating principles of the PCR process are illustrated in Figures 3 and 4 . A Thermal Cycler uses the target DNA, specific primers (short DNA segments that initiate the replication process by allowing the polymerase to bind to the DNA), the taq polymerase (which actually performs DNA replication after the primers get attached), and free A (Adenine),T (Thymine), C (Cytosine) and G (Guanine) nucleotides needed to amplify the segment of interest through repeated cycles that involve the following steps: DNA denaturation, annealing, and extension.

1) DNA Denaturation: The DNA sample to be amplified or detected is first heated to 96 0 C. At this temperature, hydrogen bonds between the bases across the two strands break, producing two complementary single-stranded DNA fragments. 2) Annealing (Hybridization): The sample is subsequently cooled to 55 0 C. This allows the primers to bind to their WC complementary segments on the two single-stranded DNA targets. The primer that binds to the forward strand is referred to as the forward primer while the one that binds to the reverse strand is referred to as reverse primer. 3) Extension: The sample is heated to 72 0 C to enable the taq polymerase to extend the primers to form two complete copies of the original double-stranded DNA molecule. Under ideal conditions, at the end of the Extension step of a cycle, the amount of target DNA doubles. This setting is illustrated in Figure 3 . However, due to several factors [21] including the efficiency of denaturation, primer annealing affinity, polymerase binding strength, and others, the DNA content may not double during each cycle. For example, denaturation requires heating the sample to a higher temperature which by itself may cause oxidative and other damages to the DNA being amplified. The efficiency of denaturation is measured in terms of the concentration of viable single-stranded DNA present after heating.

During the primer annealing stage, single-stranded DNA strings previously denatured can anneal back, therefore prohibiting access to the primer segments. The primer annealing efficiency is captured by the proportion of single-stranded DNA with bound primers. When the polymerase binds to the DNA-primer complex it forms a potentially unstable tertiary complex in which the polymerase can disassociate in a stochastic manner. The polymerase binding efficiency is captured by the fraction of tertiary products in the assay. The tertiary complexes formed during the early stage of a cycle are more likely to result in complete double-stranded DNA compared to those formed in a later stage of the cycle, due to cycle timing issues. This effect is captured through what is known as the extension efficiency of PCR.

These effects jointly contribute towards the reduction of the average efficiency of DNA amplification, which goes down from the expected doubling factor to some value ă 2, usually written as p1`ηq, where η is referred to as the cycle efficiency. The doubling of the target material at every cycle corresponds to η " 1. At the end of i cycles, a sample with concentration x DNA strands is amplified to a sample with concentration xp1`ηq i . More precisely, the cycle efficiency depends on the cycle number. Consequently, a more accurate amplification model should use the factor η j for cycle j, so that the amplified concentration after the i th cycle reads as x¨Π i j"1 p1`η j q. It is also known that η j decreases with j, which may be attributed to the fact that the primers used for amplification are more and more integrated into the DNA products and that the efficiency of the polymerase decreases. At the same time, for a small number of cycles (usually i ď 10) the DNA products are hard to detect. As a result, it is a common practice to run 30´40 cycles of PCR, depending on the expected original concentration of the double-stranded DNA to be amplified.

Note that the polymerase can also be active at temperatures below 72 0 C, thereby initiating the extension process. However, the polymerase is nonspecific at lower temperatures and leads to amplification of nonspecific DNA strands. The high concentration of the stronger and more stable GC bonds in the DNA strands hinders effective denaturation at 96 0 C. Regions with high GC bond concentration also form secondary products that prevent primer bonding [39] . These phenomena all jointly contribute to "noise" in the amplification PCR process which is not associated with the cycle efficiency. Additional sources of noise such as CCD thermal noise and shot noise can lead to a further decrease in the reliability of data points at low signal levels [40] .

Also, primers may fail to attach to the DNA if the corresponding DNA primer regions contain mutations (indels or point mutations). Since the error is caused by the actual DNA sample strand, and not the PCR process, this phenomenon should not be considered as part of the PCR noise model. The results of a simulation that studies the effect of mutations along the primer region on PCR amplification are described in Section VII, using a collection of real genomic datasets retrieved from the GISAID database [41] .

Quantitative Real Time PCR (qPCR) is a technique used for precise analysis of viral and bacterial samples. As implied by its name, qPCR allows for the amplification process to be monitored in real-time. This is achieved by introducing fluorescent labels into the DNA products and recording the change in fluorescence with an increasing number of cycles (which also allows for estimating the number of cycles needed to detect an appropriate product). The result of a qPCR experiment is usually given in terms of an amplification curve (an example of such a graph is shown in Figure 7 , where real measurements are approximated by piecewise polynomial fragments of degree ď 10). The amplification curve plots the normalized (relative) fluorescence ∆R n against the cycle number. The fluorescence increases with the increase in the target genetic material with every cycle until the fluorescence saturates. The cycle number for which the fluorescence crosses the detection threshold (which can be defined in several ways) is referred to as the cycle threshold, and denoted by C t . Note that C t is inversely proportional to the concentration of the target material in the sample: A low C t value indicates a higher concentration of the sample we wish to detect, while a high C t value indicates a low concentration of the same or spurious amplification results. The slopes of Figure 4 : Under ideal conditions, every cycle of the PCR process should double the DNA content. Due to various factors, described in the main text, not every cycle may result in twice as many strands and an averaged efficiency factor η ă 1 is used to describe the growth rate of the PCR product. the curves most often show very small variations with the concentration of the subject but may potentially be used as further indicators of the sample load.

Real-time or qPCR is usually performed using one of the following two approaches:

‚ Dye-based qPCR. The dye-based method uses dyes that only fluoresce when bound to double-stranded DNA. Thus, at the end of each extension stage, the fluorescence increases (see Figure 5 ). The chemistry of the dyes used helps in distinguishing desired and undesired products. However, the dye-based method is often nonspecific, thereby inaccurately quantifying genetic material that is not of interest. As a result, this approach requires highly selective primers and other additional controls to provide accurate amplification curve results. ‚ Probe-based qPCR. In this technique, primers specific to the target DNA include two molecules, a fluorescent reporter dye and a quencher on its two ends. When the quencher is in close proximity to the fluorescent dye, the former molecule inhibits (quenches) the fluorescence of the latter. This is usually the case when the primer is not bound to the target (see Figure 6 ). However, when the primer is hybridized to the target and the polymerase extends the primer segment, the quencher and reporter separate out and the dye is cleaved and displaced. In its free form, it fluoresces which leads to detectable signals. The dots represent actual fluorescent levels, while the curves represent a degree-10 polynomial approximation of the measurements. Since the solid curves are approximations, the fluorescence level for a small number of cycles can be negative, which is clearly not physically possible. Simple, yet less precise piecewise linear and quadratic curves will be described when discussing error models for real-time PCR. Also, note that the fluorescence saturates after roughly 35´40 cycles which shows that models that use the final cycle fluorescence cannot distinguish viral loads. Another observation is that due to the stochastic nature or RT-PCR it usually takes around 5´10 cycles to obtain visible fluorescence, independent of the viral load. Both of these features demonstrate the highly nonlinear relationship between the viral load and the fluorescence. study [42] . Viral loads in infected individuals tend to follow a "typical" inverted-V dynamics shown in Figure 9 . There, it can be seen that an individual tested 3´5 days after the infection may have a viral load that is large enough to mask any other individual tested by the same test under the GT framework. This is a sensitive issue for SQGT schemes as the C t curves may have multiple interpretations: As an example, the same C t value may correspond to 10´100 individuals tested 5´6 days after infection or one individual tested 3 days after infection. There are multiple possible ways to mitigate this problem: First, given that high viral loads very often positively correlate with observable disease symptoms [43] , 5 asking individuals about symptoms before scheduling the tests (as is, for example, done at UIUC [44] ) allows one to determine if the individual should Given a number of amplification curves used for calibration in a specific lab, the quantization regions in this example are chosen based on the intersection of the fluorescence detection level 500 and the calibration amplification curves. A C t value for a particular experiment is placed in the quantization region bounded by the two "closest" amplification curves used for calibration and their underlying C t values, or into the corresponding quantization bin. In this particular example, except for the quantization regions corresponding to the early and late cycles, the quantization regions are of nearly-uniform length. Note that the larger the C t value, the lower is the viral load. Also, if one were to only use the fluorescence levels observed at the final RT-PCR cycle (i.e., cycle number "40), the results would be noninformative with respect to the viral load as a strong saturation effect comes into existence. be group-tested or not. Another approach is to perform adaptive testing where samples with large viral loads are subjected to additional screenings, as is done in one of our proposed methods. Specialized testing strategies for pooled measurements with high viral loads can also be devised using heavy-hitter detection methods [45] .

As an abstraction, and only for our worst-case analysis we assume that each individual is represented by a viral load equal to the expected value over the tested population. In this case, the test outcome can be translated into an interval in which the number of infected individuals lies. Hence, the assumption in this case is that one can convert C t values into a rough estimate of the number of infected people in the test. For probabilistic testing, we do not have to rely on such assumptions as the testing scheme itself can be easily adapted to handle heavy hitters. 

In what follows, we provide concise overviews of all relevant GT schemes used or proposed for potential use for Covid-19 testing: (1) Classical nonadaptive and adaptive GT; (2) Nonadaptive SQGT; (3) Threshold GT; (4) Compressive sensing (CS); (5) Graph-Constrained GT. For all these methods, we describe their potential advantages and drawbacks and then proceed to introduce a new method, which we refer to as adaptive SQGT. Adaptive SQGT with a "curve fitting"-based noise model appears to provide the theoretical state of the art GT results for qPCR test models and is the focus of our subsequent discussions.

The assumptions are as follows: In a group of n individuals, there are d infected people. When a subset of people are tested, the result is positive (e.g., equal to 1) if at least one person in the tested group is infected, else the test result is negative (e.g., equal to 0). Such a testing scheme is referred to as binary, as the outcomes take one of two values (see Figure 1 (a)). GT aims to find the set of all infected people with the fewest number of binary tests possible and may use nonadaptive and adaptive tests. In the former case, all tests are performed simultaneously and the outcome of one test cannot be used to inform the selection of the individuals for other tests. In the adaptive setting, one can use multiple stages of testing and different combinations of individuals to best inform the sequentially made test choices.

When d ! n, it is well-known that Ωpd¨logpn{dqq number of tests are required to find all infected individuals. Furthermore, it was shown in [46] that for NAGT, at least Ωpd 2¨l ogpnq{ logpdqq tests are required. For the same parameter regime, there exist explicit nonadaptive schemes that require Opd 2¨l ogpn{dqq tests to find the infected group [47] . A four-stage adaptive scheme that uses an optimal number of tests that meets the lower bound was recently described in [48] . Of special interest is the classical binary search result of [49] which established an elegant adaptive scheme that differs from the information-theoretic limit only by an additive Opdq term.

Despite the many proposed applications of this model to Covid-19 testing, it is obvious from the previous discussion that the GT measurement outcomes do not fully use the actually available qPCR results. One could argue that the fluorescence exceeding the detection threshold may correspond to the test outcome 1, but clearly, significantly more information is available as the detection threshold depends on the concentration of the viral cDNA and hence the number of infected individuals. This motivates using a more quantitative GT approach, already introduced under the name of SQGT.

In SQGT, one is given a collection of thresholds 0 " τ 1 ă τ 2 㨨¨ă τ r , and the outcome of each test is an interval pτ i , τ i`1 s, where 0 ď i ď r´1. The outcome of an experiment cannot specify the actual number of infected individuals but rather provides a lower and upper bound on that number, τ i´1 and τ i , respectively. If τ i " τ i´1`1 for all values of i and r " d, the scheme is referred to as additive GT, or the adder model [35] , [36] . The two models are depicted in Figure 1 (b) and (c). The additive test model described in [36] requires 2¨pn{ log nq tests to determine all possible infected individuals, for 0 ď d ď n.

Another special SGT case of interest assumes that the test results are additive up to some threshold τ and after that, they saturate [37] (see Figure 1 ). This model is of special interest for Covid-19 testing as it takes the warm-up/saturation information into account and, in addition, under a proper noise model, captures the fact that amplification graphs have different C t values determined by the concentration of the viral load (an hence the approximate number of infected individuals). Furthermore, one can argue that the RT-PCR fluorescence intensity information is inherently semiquantitative [30] as the fluorescence levels and C t values can be placed into bounded bins determined by the number of cycles. This observation is explained in more detail in the next section, along with new theoretical results pertaining to adaptive SQGT schemes with appropriate noise models. Figure 10 : The birth-death noise model. Here, the assumption is that the C t value can be corrupted by noise only in so far that they can be mislabeled as belonging to intervals adjacent to the correct interval (except for the values falling into the first and last quantization region or bin).

An extension of the GT problem was introduced by Damaschke in [50] : In this setting, if the number of defectives in any pool is at most the lower threshold ą 0, then the test outcome is negative. If the number of defectives in the pool is at least the upper threshold u ą , then the test outcome is positive. However, if the number of defectives in the pool is between u and , the test outcome is arbitrary (i.e., either 0 or 1). Thus, the algorithms for Threshold GT are designed to handle worst-case adversarial model errors. Note that when " 0, and u " 1, Threshold GT reduces to GT. It is known that for nonadaptive threshold GT, Opd¨g`2¨plog dq logpn{dqq tests (where g " u´ ´1) suffice to identify the d infected individuals [51] . The Threshold GT model is partly suitable for modeling the qPCR process, as the lower threshold can obviously assume the role of the fluorescence-based detection threshold, " C t ; unfortunately, due to the saturation phenomena, a specialized choice for the upper threshold u does not allow one to accurately assess the number of infected individuals in the pool. The "in-between" threshold results also make the simplistic assumption that despite the observed fluorescence value being closer to the upper threshold, one can still call the outcome negative (and similarly for the small fluorescence levels and the lower threshold).

In compressive sensing, the defectives are represented by nonnegative real-valued entries. Thus, quantitative GT represents a special instance of compressive sensing. Compressive sensing assumes that one is given an unknown vector x P R n , in which only d ! n entries are nonzero. The vector x is observed through linear measurements formed using a measurement matrix M P R mˆn , leading to an observed vector y " Mx`n, where n is the measurement noise (usually taken to be Gaussian N p0, σ 2 q). For noiseless support recovery, m " Opd¨log n d q measurements are sufficient. For exact support recovery in the noisy setting, a signal-to-noise-ratio S of Ωplog nq is required for the same number of measurements as needed in the noiseless setting [52] . Compressive sensing reconstruction is possible through linear programming methods or low-complexity greedy approaches [53] - [55] .

The recently proposed Tapestry method [56] combines group testing with compressive sensing and uses combinatorial designs (i.e., Kirkman systems) to construct the measurement matrix. However, the approach does not account for several practical features inherent to quantitative PCR. Although Tapestry proposes a model that involves multiplicative noise and converts it into additive noise through the use of a logarithmic function, it is still inherently linear: Tapestry is based on a CS framework, which is additive and applies to viral loads. But as seen from the previous discussion, PCR measurements report intersections of fluorescence level curves and a given threshold, and these values are nontrivial nonlinear functions of the viral load. Additionally, although the compressive sensing measurements used in their the work are assumed to correspond to C t values, no thresholding is used to model the actual practical process of generating the same 6 . Also, this and all other methods do not account for the stochasticity of the PCR measurements and the fact that different lab protocols may lead to different C t values when presented with the same sample mixture. The CS methods in [56] rely on Gaussian assumptions for the cycle inefficiency exponent and do not take into account that the efficiency decays with the number of cycles and with the number of potential mutations in the primer regions (see also our analysis in Section II). As many other quantitative methods, it also appears vulnerable to heavy hitters.

CS-based and many other proposed Covid-19 testing methods also do not take into account the fact that the number of RT-PCR machines/staff members is limited in virtually all test settings 7 . The unavailability of arbitrary number of PCR machines inherently suggests using adaptive testing strategies. Adaptive quantitative testing schemes for Covid-19 were reported in [60] . There, the same problem setup as in [56] is used to postulate an additive viral load model in the absence of noise. The new contribution of the work is a proposal for a two-stage testing scheme that bears a small resemblance to our methods in so far that we also propose two-stage adaptive pooling schemes. However, these techniques and the model used are different from ours since [60] employs a combination of maximum likelihood and maximum-a-posteriori estimators to determine the infected individuals in the second stage, while we employ zero-error GT and SQGT techniques to find all infected individuals. Additionally, while [60] reports the number of tests and conditional false positive and conditional false negative rates for the simulation experiments, we supplement our new tailor-made modeling and testing schemes with an in-depth theoretical analysis and performance guarantees.

Nevertheless, there seem to be multiple advantages of CS methods for Covid-19 testing: One should be able, in principle, to recover not only the infected individuals but their viral loads as well (it still remains to be seen as such approaches are feasible as reported experiments use controlled concentrations of viral loads [56] ). In particular, integer and nonnegative CS testing, along with quantized CS approaches can impose model restrictions on such testing schemes [58] , [61] to render them more suitable for the problem at hand.

Let G " tV, Eu be a graph with vertex set V, |V| " n, and edge set E, representing a connected network of n people out of whom d are infected. In graph-constrained GT, vertices participating in the same test are restricted to form a path in the graph [62] . This model is relevant as it can be adapted to require that only individuals that did not have contacts with each other are tested together (one only has to apply the problem to the dual of the contact graph used in Covid-19 testing). This allows us to identify individuals that fell ill in an "independent" fashion rather than through contact with each other. If Tpnq denotes the mixing time of the random walk on the graph, and c " ∆ max ∆ min is used to denote the ratio between the maximum degree and the minimum degree of the graph, then no more than Opc 4¨d2¨T2 pnq logpn{dqq tests are required to find the set of infected vertices. For example, a complete graph (Tpnq " 1, c " 1) requires no more than Opd 2¨l ogpn{dqq tests since it corresponds to the classical GT regime. Unfortunately, graph-constrained GT requires a significantly higher number of tests than classical GT methods as the tests are inherently restricted. As a result, despite the fact that this scheme is a natural choice for problems such as network tomography where these constraints need to be satisfied, it is not a proper choice for Covid-19 testing. Another "community-constrained" (although without an underlying interaction graph) was recently proposed in [29] and is discussed in the next subsection.

Several lines of work have focused on what is now known under the name of community-aware GT. In [29] , [63] , the authors leverage correlations arising due to the presence of community structures to reduce the number of tests and increase the reliability of testing. More precisely, they assume that a community of n members has d ! n infected individuals and that the population is partitioned into F families. In the combinatorial infection model, it is assumed that d f families have at least one infected individual and that all the members of the remaining families are infection-free. An infected family indexed by j is assumed to have d pjq infected members so that d "

The testing scheme can be succinctly described as follows: A representative individual from each family is selected uniformly at random. The representative community members are tested using either an adaptive or a nonadaptive GT algorithm. Family members whose representatives tested positive are tested individually. Members from the remaining families are tested together using either an adaptive or a nonadaptive GT scheme. The first approach proposed in [29] did not account for inter-community interactions, but that issue was subsequently addressed in [64] .

In a related line of work, the authors of [65] establish how correlations in samples that arise due to the ordering of the tested individuals in a queue save in terms of pooled testing costs. In particular, the authors assume that in the first stage of Dorfman's testing scheme, the samples that are pooled and tested together are correlated. They model the correlation through the use of a random arrival process [65] . The expected number of tests required to identify all infected individuals for their modified Dorfman scheme is compared against the expected number of tests required by the classical Dorfman testing scheme in which samples that are tested together are picked at random. The authors show that under certain conditions, the expected number of tests required by the modified Dorfman testing scheme does not exceed the expected number of tests required by the original scheme. Under additional conditions, the authors derive a closed form expression that captures the savings available for correlated samples. Furthermore, [65] considers an underlying social contact graph, and proposes an hierarchical agglomerative algorithm to identify individuals to be pooled together in the first stage of the modified Dorfman testing scheme. This line of work is closely related to the problem of identifying bursts of defectives, first introduced in [66] and analyzed for the case of a single burst.

We take a different approach to using community-structures for GT in so far that we suggest to quickly identify heavily infected (heavy hitter) families and then quarantine members of such communities. To the best of our knowledge, this is the first GT problem formulation that also takes into account strategies for mitigating the spread of a disease, such as self-isolation. We address this question in the context of classical GT in Section VI.

Before proceeding with the original contributions, we remark that all the above GT techniques and scheduling models have probabilistic counterparts in which each individual is assumed to be infected with the same probability p [6] or members of different communities are infected with different probabilities, p i , i " 1, . . . , F [33] . The latter setting is especially important when prior information about the individuals is known (for example, their risk groups, potential symptoms etc). For an excellent in-depth review of these and some other GT schemes, the interested reader is referred to [7] .

IV. AC-DC: NEW AMPLIFICATION CURVE BASED ADAPTIVE SCHEMES -THE PROBABILISTIC SETTING Next, we introduce two adaptive SQGT schemes, one which is suitable for probabilistic testing and another one that is worst-case and nearly-optimal from the information-theoretic perspective. In the former case, considered in this section, a simple two-stage testing scheme is designed and analyzed with the goal of enabling practical implementations of adaptive SQGT. The results are described for two thresholds only, but a generalization is straightforward. This scheme also allows for incorporating heavy hitters into the testing scheme, which is of great practical relevance. In the worst-case, which is considered in the section to follow, the schemes extend the ideas behind Hwang's generalized splitting [49] in two directions that lead to algorithms using what we call parallel and deep search, respectively. In both settings, the outcomes of the first round of testing inform the choice of the composition of the test in the rounds to follow. The methods are collectively referred to as the AC-DC schemes, in reference to the use of the information provided by the amplification curve (AC) during the process of diagnostics of Covid-19 (DC). A relevant observation is that the worst-case adaptive schemes allow for using nonuniform amounts of genetic material from different individuals, which may be interpreted as using nonbinary test matrices.

We describe next a simple probabilistic two-stage AC-DC scheme that significantly improves upon the original single-pooling scheme of Dorfman and builds upon the SQGT framework. The underlying idea is to follow the same overall strategy as in the single-pooling scheme, but exploit the SQ information obtained in the first stage to perform better-informed testing in the second stage (i.e., dispense with individual testing of all individuals that feature in infected pools as part of the second stage).

Consider a scenario where we have access to semiquantitative tests that return one of three values: If no individual featured in the test is positive, the test returns 0. If between 1 and τ individuals are positive, for some threshold τ ě 1, the test returns 1. Finally, if more than τ individuals test positive, the test returns 2. This scheme can be interpreted as follows: Suppose that C t is the observed cycle thresholds (defined in Section II-C for a particular test). If C t ą c 1 for some large threshold c 1 , we say that the outcome is 0 as the potential viral or viral-like contamination load is too small to claim the presence of an infected individual. If c 2 ď C t ď c 1 , we say that the output is 1 and based on the average viral load, convert this into the maximum possible number of infected individuals τ. If C t ă c 2 , we say that the output is 2 and that more than τ individuals in the pool are affected.

For the new single-pooling AC-DC scheme, we assume that the population contains n individuals, each of which is independently positive with some probability p (Which can be easily determined based on regional infection rate reports: For example, at UIUC in September/October 2020 [44] , p » 0.05), and proceed as follows:

1) Stage 1: Divide the n individuals into n{s disjoint pools S 1 , . . . , S n{s , each of size s; 2) Stage 2: If a pool S i tests 0, then immediately set the status of all individuals P S i as "negative". If a pool S i tests 1, then apply a nearly-optimal zero-error nonadaptive group testing scheme to detect the t infected individuals in S i . (Such a testing scheme is simple to design: It suffices to sample a random binary matrix where all entries are i.i.d. according to some Bernoullipqq distribution, 0 ă q ă 1. This is so since the resulting matrix will be a zero-error NAGT scheme with high probability provided the number of rows is large enough.) If a pool S i tests 2, then test all individuals P S i separately. Given the description above we can compute the expected number of tests per individual of the testing scheme, T{n, as a function of the probability of infection p, the first-stage pool size s, and the threshold τ. Using the fact that the zero-error nonadaptive GT schemes we use in the second stage can be designed with mps, τq " c¨τ 2 logps{τq tests, we conclude that

where p 1 " Prr1 ď Bps, pq ď τs and p 2 " PrrBps, pq ą τ`1s denote the probability that a given pool tests 1 and 2, respectively. Here, Bps, pq stands for a binomial random variable with s trials and success probability p.

A particular case of interest pertains to setting τ " 1 in (1). For a small probability of infection p, the optimal threshold τ is close to 1 which justifies this choice. In this case, we have p 1 " s¨pp1´pq s´1 and p 2 " 1´p1´pq s´s¨p p1´pq s´1 . Moreover, it is well-known that, for any s, there exists a simple (and optimal) zero-error nonadaptive scheme for finding 1 defective among s items using mps, 1q " rlog ss tests (namely, set the i-th column of the test matrix to be the binary representation of i, i.e., use a Hamming code parity-check matrix for testing). Combining these observations together with (1), we conclude that the expected number of tests per individual when τ " 1 equals

On the other hand, the expected number of tests per individual for the basic single-pooling scheme [6] is

and the expected number of tests per individual for the double-pooling scheme [9] is

We compare the optimal expected number of tests per individual (as a function of p) achieved by our semiquantitative singlepooling scheme with τ " 1 (given in (2)) and the single-and double-pooling schemes (given in (3) and (4), respectively) in Figure 11 . Semiquantitative single-pooling outperforms the other methods considered here as shown in the figure. This is in particular true for p ď 0.05, which we already pointed out corresponds to a practical parameter value. There are two directions to further improve our scheme:

‚ We can easily extend the simple ideas presented above to obtain a semiquantitative version of double-pooling, and, more generally, multi-pooling schemes. The algorithm for this setting is summarized below: 1) Stage 1: Repeat Stage 1 of the previous semiquantitative scheme twice in parallel. We say an individual tests pa, bq if its first pool tests a and its second pool tests b. Figure 11 : Comparison between the expected number of tests per individual required by Dorfman's single-pooling scheme [6] , the Broder-Kumar doublepooling scheme [9] , and our semiquantitative single-pooling scheme.

If an individual tests p0, bq or pa, 0q, immediately mark it as negative;

If an individual tests p1, 1q or p1, 2q, then apply a zero-error nonadaptive GT scheme for τ defectives to its first pool.

If an individual tests p2, 1q or p2, 2q, test them individually.

‚ We may also improve the performance of our semiquantitative scheme by introducing more (sufficiently small) thresholds τ 1 ă τ 2 㨨¨ă τ and extending the original idea in a natural way: If a pool has between τ i´1 and τ i infected individuals, then apply a nearly-optimal zero-error NAGT scheme that detects τ i infected to the pool in question.

It is also simple to analyze how the SQGT scheme from the previous section performs when infected individuals may have either low or high viral loads, i.e., it is straightforward to account for heavy hitters. To this end, we consider a simplified model where each individual is independently infected and presents a low viral load at the time of testing with probability p i1 , or is infected and presents a high viral load at the time of testing with probability p i2 . In particular, each individual is infected (regardless of her/his viral load) with total infection probability p " p i1`pi2 ă 1.

As already explained, individuals with high viral load are problematic because, based on the SQ output of RT-PCR, pools featuring one such individual may be mistaken for pools with several infected individuals with low-to-average viral load. 8 This phenomenon naturally leads us to consider the following modified version of the testing method studied in Section IV-A: A test applied to a pool of individuals has outcome 0 if there are no infected individuals in the pool, outcome 1 if there exists exactly one infected individual with low viral load, and 2 if either there exists more than one infected individual with low viral load, or at least one infected individual with high viral load. Therefore, as expected, individuals with high viral load obfuscate the test outcomes.

We consider now the SQGT scheme described in Section IV-A with τ " 1 and under the heavy-hitter model. The probability that a pool of size s contains exactly one infected individual with low viral load and zero individuals with high viral load (leading to test outcome 1) is

while the probability that the pool contains either more than one infected individual with low viral load or at least one individual with high viral load is

Combining these observations with the reasoning from Section IV-A, we conclude that the expected number of tests per individual as a function of p i1 and p i2 is given by

where p " p i1`pi2 . For fixed p i1 and p i2 , it is easy to numerically minimize the expression above as a function of s to find the optimal pool size for the scheme under consideration. Figures 12 and 13 compare the expected number of tests per individual required by different schemes for different values of the total infection probability p and the specific infection probabilities p i1 and p i2 . The most practically relevant pair of parameters can be obtained from Figure 12 , under the assumption that heavy hitters are individuals who have viral loads above 10 6 . Thus, by approximating the nonlinear portion of the viral load curve by a linear function, one can easily show that the probability that an infected individual is a heavy hitter is proportional to the area of the highlighted triangle, and approximately equal to 0.16 (which is used in Figure 12 ). Note that the reduction in the number of tests increases with p, and for p " 0.05, which is a realistic infection rate, the savings compared to nonquantitative testing are larger than 5%.

Although we considered only an SQ single-pooling scheme in this section, these ideas can be easily extended to upgrade multi-pooling schemes with binary testing (such as the one from [9] ) to exploit SQ test information under a variable viral load. This would allow one to further improve on the expected number of tests required by [9] . [6] , the Broder-Kumar doublepooling scheme [9] , and our semiquantitative semi-pooling scheme as a function of total infection probability p with p i1 " 0.84p, p i2 " 0.16p. [6] , the Broder-Kumar doublepooling scheme [9] , and our semiquantitative semi-pooling scheme as a function of total infection probability p with p i1 " 2p{3 and p i2 " p{3.

The above described probabilistic setting can be generalized to account for different priors for different individuals by invoking the generalized binomial group testing scheme. Recall that Dorfman's scheme assumes that each individual has a probability p of being infected, independent of everyone else. The set of individuals is partitioned into groups of size s, and each group is tested once. The group size s is selected to minimize the number of expected tests.

Hwang extended this setting in [33] to account for the varying prior probabilities of infection. In this setting every individual i P t1, 2, . . . , nu is assumed to have probability p i of being infected, and thereby a probability of q i " 1´p i of not being infected. Clearly, in this generalized setting, a (possibly random) partitioning of the individuals into groups of equal sizes is no longer the optimal strategy to for the first round of testing.

To find the optimal partition of the individuals in the generalized binomial setting, without loss of generality, one may assume that the individuals are reindexed so that 0 ă q 1 ď q 2 ď . . . ď q n ă 1.

Given a subset of individuals to be tested, G Ď t1, 2, . . . , nu, let TpGq denote the expected number of tests required to find the set of infected individuals in G by first jointly testing all the individuals in the group G and then testing every member of G individually if the first test is positive. This number equals:

Now, let DpU q " tG 1 , G 2 , . . . , G k u denote the optimal partition of the population U to be tested, where |U | " n. Let CpU q denote the total expected number of tests required to run the two-stage testing procedure on the optimal partition. Clearly, CpU q " ř k i"1 TpG i q. Furthermore, let U m denote the set of m individuals with the highest probability of being infected, i.e., individuals indexed by t1, 2, . . . , mu. The optimal partition and the corresponding expected number of tests can be found by solving the following optimization problems:

where L denotes the size of the largest group/part in DpU m´1 q. At step m of the optimization procedure, the probabilities tp j u jďm and the previously computed CpU j q are used to determine DpU m q and the expected number of tests CpU m q of the population U m . As a consequence of the structure of the program, one has the following property for the optimal partition: If individuals i and j, j ą i, are in the same group, then all individuals k such that i ă k ă j are in the same group as well (a simple induction argument can be used to prove this claim). Next, assume that the population has only two types of individuals: m individuals that have a high p 1 probability of infection, and the remaining n´m individuals that have a low p 2 ! p 1 probability of infection. Exploiting the structure of the optimization program and the fact that only two types of individuals are present in the test pool, the optimal number of tests needed to find the set of infected individuals using the two-stage procedure equals: 

We conclude our exposition in this section by presenting a theoretical result that establishes lower bounds for nonadaptive probabilistic GT that may be used to assess the quality of our adaptive schemes. For this purpose, we adapt an argument by Aldridge [67] for arbitrarily small error probability under a constant probability of infection. More precisely, we consider a setting where each test has m`1 outcomes for some m ě 1: The outcome of a test is either i if there are exactly i infected individuals for i ă m, and ě m otherwise. This corresponds to the setting introduced in [37] which provides the most informative type of measurements one can expect from the SQGT framework using the amplification curve information. This model accounts for the saturation limit for each test, dictated by m, which is a phenomenon observable from the amplification curve. Moreover, as before we assume that each individual in the population of size n is infected independently with some constant probability p ą 0. We show the following.

Theorem 1 For every m and constant p ą 0 there exists a constant pm, pq ą 0 such that, under the setting described above, nonadaptive testing requires at least n{m tests to achieve error probability less than pm, pq in a population of size n.

In contrast, for m " 2, our two-stage scheme uses significantly fewer than n{2 tests provided p is not very large.

Proving Theorem 1 follows by a simple adaptation of an approach by Aldridge [67] , who showed that individual testing is required in order to achieve arbitrarily small error in regular nonadaptive probabilistic group testing (which corresponds to m " 1). First, given any nonadaptive testing scheme, we may without loss of generality remove all tests with m or fewer elements, along with all individuals who participate in those tests. This does not affect the lower bound. Then, we show that there are no nonadaptive testing schemes with an arbitrarily small error where every test includes at least m`1 individuals. Combining these two observations immediately yields Theorem 1.

For an individual i, let x i denote its infection status. Call an individual i (regardless of its infection status) disguised if every test t in which it participates contains at least m other individuals which are infected. If i is disguised, then changing x i from 0 to 1, or vice-versa, does not change the outcome of the testing scheme. As a result, we can do no better than guess x i , and we will be wrong with probability at least minpp, 1´pq. To finalize the argument, it suffices to show there is a disguised individual with constant probability.

Let D i denote the event that individual i is disguised, and let D t,i denote the event that individual i is disguised in test t. Since the D t,i are increasing events 9 , the Fortuin-Kasteleyn-Ginibre (FKG) inequality [68] implies that

where x t,i indicates whether individual i participates in test t. Moreover, we have PrrD t,i s " PrrBpw t´1 , pq ě rs,

where w t " ř n i"1 x t,i is the weight of test t.

L i " log¨ź t:x t,i "1 PrrD t,i s‚" ÿ t:x t,i "1 log PrrD t,i s "

where T denotes the total number of tests, which we assume satisfies T{n ă 1. Then, it suffices to show that there exists some i ‹ with L i ‹ ą c for some constant c independent of n. Let I be uniformly distributed over t1, 2, . . . , nu, and let L " ErL I s. where the second equality follows from the fact that PrrD t,i s is the same for every i such that x t,i " 1, and in the first inequality we use the assumption that T{n ă 1. It is immediate that there exists some i ‹ with L i ‹ ě L, which implies that PrrD i ‹ s ě 2 L ‹ . Therefore, the error probability of the testing scheme is at least pm, pq " minpp, 1´pq¨2 L ‹ . Noting that L ‹ does not depend on n and is bounded from below for any m and p (since lim wÑ8 w log PrrBpw´1, pq ě ms " 0) concludes the proof.

As before, we assume that we are given a set of n samples with at most d infected individuals. Our goal is to minimize the number of tests needed to identify all infected individuals and we do not impose any restrictions on the "simplicity" of our scheme. As a result, we consider a generalization of the model described in the previous section which allows for more than three test outcomes.

For simplicity, as well as for practical reasons 10 , we focus on equidistant thresholds but allow for warm-up/saturation effects. We refer to this model as the saturation GT scheme.

Let τ, m P Z`represent the distance between the thresholds and the number of thresholds, respectively. Denote the outcomes of the test by a nonnegative integer t ď m. Then,

if the number of infected individuals is between 1 and τ, 2, if the number of infected individuals is between τ`1 and 2τ, . . . . . . m´1, if the number of infected individuals is between pm´2qτ`1 and pm´1qτ, or m, if the number of infected individuals is at least pm´1qτ`1.

We seek to identify d infected individuals from a population of size n given that each test returns a value in (10) . We refer to this problem as the pn, dq adaptive SQGT problem or the pn, dq-ASQGT problem for short. Another way of looking at (10) is that if the collection of samples tested contains d 1 infected individuals, then the output of the test is r d 1 τ s when d 1 ď mτ and m otherwise. Note that for every test there are m`1 possible outcomes and the output of a test tells us roughly (within at most τ) how many total infected samples are part of the tested pool of samples.

Remark 2. Note that this model differs from the model introduced in Section IV since as m increases the widths of our threshold remain the same whereas in Section IV the widths changes as the number of thresholds increases. Despite this difference, and as will be discussed in Example 18, the ideas discussed here are applicable to the case where the widths of the thresholds are nonuniform.

Let 2 β " m`1. Motivated by practical applications, we will be interested in the case where β " Op1q. Our main results are two algorithms, which we refer to as parallel search and deep search. Parallel search is applicable for the setting d ą β. In Lemmas 6 and 7, we show that using parallel search it is possible to efficiently identify from a set of pools (each of size s " 2 α and large enough to contain at least β infected individuals) a set of β defectives using at most α tests. Note that as a first-step simplification, one may think of n being approximately equal to d¨2 α ; the notation involving α is chosen to enable a comparison between our SQGT search scheme and the well-known splitting approach by Hwang [69] . Deep search, discussed in Lemma 10 and applicable for the setting d ă β, shows that it is possible to identify all d infected individuals using roughly d¨α β´logpβq tests. Our main result is Algorithm 1, which for d " Ωpnq shows that one can identify d infected individuals using at most d β¨p α`3`log βq tests. These results show that adaptive SQGT roughly provides β-fold savings in the number of tests when compared to classical adaptive GT. Furthermore, they differ from the information-theoretic lower bound (as it applies to ASQGT) of Lemma 4 by Op d β q tests. It remains an open problem to identify whether it is possible to solve the pn, dq-ASQGT problem using fewer tests.

We start with the following obvious claim, which allows us to restrict our attention to the case where τ " 1 and simplifies the problem at hand. Claim 3. Let G be the set of test subjects and suppose that there are at most d infected individuals within this group. Let P p1q be a pool formed by taking one sample from each individual in G and let P pwq be a pool formed by taking w samples from each individual in G. Let t p1q be the output of testing P p1q under the setup pm, τq " pm, 1q and let t pwq be the output of testing P pwq under the setup pm, τq " pm, wq, according to ( 10) . Then, t p1q " t pwq .

Next, we present a lower bound (i.e., information-theoretic or counting lower bound) on the number of tests necessary to solve the pn, dq-ASQGT problem. The result follows from a simple counting argument and is consistent with the result from Claim 3, as it does not depend on the width τ of the threshold. Lemma 4. Let n " p2 α`1 q¨d`2 α¨δ`∆ , where α, δ, ∆ are integers, δ ă d, and ∆ ă 2 α . Then, the number of tests Lpn, d, mq needed to identify the infected individuals is bounded as:

Proof: The number of ways to select at most d infectives in a group of n individuals is ř d i"0`n i˘. Thus, we have

The next example illustrates a simple approach for addressing the ASQGT problem, and motivates the analysis that follows. From here on, we write rrxss " t0, 1, . . . , x´1u and rxs " t1, . . . , xu.

Example 5. Suppose that we are given a collection of n individuals with exactly d infected subjects. We start by randomly partitioning the set of n individuals into d groups each of size s " n d " 2 α , where we assumed for simplicity that d|n. The expected number of infected individuals in each group is 1.

Denote the d groups or pools by G 0 , G 1 , . . . , G d´1 ; all groups have the same size and from this point on, for simplicity, assume that each group contains exactly one infected subject. For i P rrdss we proceed as follows. We partition G i into 2 β groups of equal size and denote the subgroups as G i , j P rr2 β sszj ‹ is free of infected individuals. Next, we form a new set of pools, which we denote by P i , i P rrdss, comprising k replicas of the samples in G pkq i , for all k " 0, . . . , 2 β´1 . Let t i denote the output of the semi-quantitative test described in ( 10) after the pool P i is tested. Then, it is straightforward to observe that the outcome t i is j ‹ , and hence we can identify the group which contains the one single infected individual using only one nonbinary outcome test. We repeat this procedure for each group G i , i P rrdss, partitioned into subgroups. It can be hence seen that it is possible to identify d infected individuals using only d α β tests assuming each of the d groups of size 2 α each contain exactly one infected subject. l

To make this argument rigorous, we need to account for the fact that not every group will have exactly one infected individual. In this case, upon creating the subpools we have to recursively test them until we identify a prescribed number of infected individuals. In fact, the approach from the previous example is a special case of what we refer to as deep search, described in Lemma 10. The resulting algorithm is summarized in Algorithm 1, and it requires roughly an additional factor of Op d β q tests compared to the information-theoretic lower bound.

We start by introducing some useful notation. Suppose that G 1 is a subgroup of individuals to be tested and that the outcome of a test governed by (10) is t. In this case, we say that G 1 is a t-infected group. When referring to an ordered collection of groups pG 0 , G 1 , . . . , G g´1 q, we say that the collection is a pt 0 , t 1 , . . . , t g´1 q-infected group if t 0 ě t 1 쨨¨ě t g´1 and G i is a t i -infected group, for i P rrgss. We also say that pG 0 , . . . , G g´1 q is a β-minimal group if ř g´2 j"0 t j ă β, but ř g´1 j"0 t j ě β. The following lemma constitutes the key component of one of our approaches to solving the pn, dq-ASQGT problem. We refer to the procedure described in the proofs of the next two results as parallel search.

In the first lemma below, we make the simplifying assumption that a group is β-minimal and g " β. Afterward, in Lemma 7 we consider the case when g ă β.

Lemma 6. Let α and β be positive integers. Suppose that pG 0 , G 1 , . . . , G β´1 q is a β-minimal group, where g " β, and that each group has size at most 2 α . Then, we can identify β infected individuals in the group using at most α tests.

Proof: We prove the result by induction on α, where 2 α as before is the size of each subgroup. Recall that under this setup t 0 " t 1 "¨¨¨" t g´1 " 1 and g " β.

First, consider the case α " 1, for which we have β 1-infected groups of individuals and each group has size 2. For shorthand, denote the β infected groups as G 0 , G 1 , . . . , G β´1 . From these β groups, we form a "super-pool" of samples which contains a total of 2 0`21`22`¨¨¨`2β´1 " 2 β´1 samples. More precisely, for i P rrβss, the super-pool contains 2 i samples from one individual P G i . Since t 0 " t 1 "¨¨¨" t β´1 " 1 and τ " 1, according to (10) the output returned after testing this super-pool of samples is a number t between 0 and 2 β´1 . Let b 0 , b 1 , . . . , b β´1 be the binary representation of the number t. It is straightforward to verify that b i " 1 then the individual selected from G i is infected. Otherwise, if b i " 0, then the above described individual is not infected, which implies the other individual (the one not tested) in group G i is infected. Thus, we conclude the statement in the lemma holds when α " 1.

For the inductive step, assume that the statement holds when the group size is at most 2 α 1 and consider the setup where the group size is 2 α " 2 α 1`1 . We follow the same approach as described for α " 1 for creating super-pools. Under this setup, we have β 1-infected groups G 0 , G 1 , . . . , G β´1 , each of size 2 α 1`1 . For i P rrβss, let Q i Ď G i be a subset of G i of size 2 α 1 . Next we construct a super-pool that contains 2 i samples from each individual in Q i , i P rrβ´1ss. Let t denote the output of testing this super-pool according to (10) , where b 0 , b 1 , . . . , b β´1 is the binary representation of t. As before, if b i " 1, then Q i has a single infected individual. Otherwise, if b i " 0, then there is an infected individual in the set G i zQ i which also has size 2 α 1 . For i P rrβss, let G 1 i " Q i if b i " 1 and otherwise, if b i " 0, set G 1 i " G i zQ i . Then, pG 1 0 , G 1 1 , . . . , G 1 β´1 q is a p1, 1, . . . , 1q-infected group and we can apply the inductive hypothesis to pG 1 0 , G 1 1 , . . . , G 1 β´1 q. For the case g ă β, we use a similar partitioning idea to identify at most β subgroups which satisfy the conditions in the lemma. The difference between the approaches is that for g ă β the number of samples added into the pool is dictated by a mixed-radix representation (in which the numerical base varies from position to position) rather than a binary representation. For simplicity, we assume from now on that β is an even integer although the results hold for odd integers as well.

Lemma 7. Let α, β, g be positive integers such that g ă β. Suppose that pG 0 , G 1 , . . . , G g´1 q is a β-minimal group and that each group has size at most 2 α . Then, we can identify β infected individuals using at most α tests.

Proof: We begin with the following claim which we find useful in our subsequent discussion.

Claim 8. Suppose we are given a sequence pt 0 , . . . , t g´1 q P rrβ`1ss g , where g ă β, and the values t 0 ě t 1 쨨¨ě t g´1 are such that ř g´1 j"0 t j ě β, but ř g´2 j"0 t j ă β. Furthermore, let pn 0 , . . . , n g´1 q P rrt 0`1 ssˆrrt 1`1 ssˆ¨¨¨ˆrrt g´1`1 ss. Then, the number of different choices for pn 0 , . . . , n g´1 q is at most 2 β .

Proof of Claim 8: First, consider the case g ď β 2`1 . Since ř g´2 j"0 t j ă β, it follows that t g´2 ď β g´1 and, from the assumptions stated in the claim, t g´1 ď t g´2 ď β g´1 . The total number of possibilities for pn 0 , . . . , n g´1 q restricted to the first g´1 components is maximized when t 0 " t 1 "¨¨¨" t g´2 , which implies that the total number of possible choices for the i-th component of the sequence when i P rrg´1ss equals β g´1`1 . Therefore, the total number of possibilities for the constrained sequences isˆβ

which follows since´β g´1`1¯g is increasing with g and g ď β 2`1 . Since 3 β{2`1 ď 2 β whenever β ě 8, we conclude that the result holds for β ě 8. For the case where β ă 8, the result can be verified through exhaustive checking.

Next, we consider the case g ě β 2`1 . Note that under this setup, since t 0 ě t 1 쨨¨ě t g´1 , it follows that t g´1 " 1. Otherwise, if t g´1 " 2, we would have ř g´2 j"0 t j ě β.

For this case, we prove the result by induction on g. The base case, corresponding to g " β 2`1 , follows from the previous paragraph. Therefore, assume that the result holds for all g ă γ and consider g " γ ą β 2`1 . Since γ ą β 2`1 , we have t γ´2 " t γ´1 " 1 which implies that ř γ´3 j"0 ă β´1, since otherwise, if ř γ´3 j"0 " β´1, then ř γ´2 j"0 t j " β and we arrive at a contradiction. Thus, we have γ´1 ě β´1 2`1 and so we can apply the inductive hypothesis to the first γ´1 components of the sequence pn 0 , . . . , n g´1 q and conclude that there are at most 2 β´1 possible choices for the sequence pn 0 , n 1 , . . . , n γ´1 q. Since t γ´1 " 1, it follows that the total number of different options for the sequence pn 0 , n 1 , . . . , n γ´1 q is at most 2¨2 β´1 . This completes the proof.

Recall the main idea behind the proof of Lemma 6, where we tacitly assumed that g " β. There, we used the binary representation of the integer t, where t denotes the test outcome of the super-pool, to determine which of the tested subgroups involved infected individuals. In order to make this argument work, we formed the super-pool by adding 2 i samples from group Q i Ď G i for i P rrβss, where |Q i | " |G i | 2 . Next, the idea is to add N i samples from each group, where N i is chosen by considering a mixed-radix representation of the number t.

We say that pb 0 , b 1 , . . . , b g´1 q is the pt 0 , t 1 , . . . , t g´1 q-mixed radix representation for t if the following is true. Let N 0 " 1. For i P rg´1s, let N i " pt i´1`1 q¨N i´1 . Note that when t 0 " t 1 " t 2 "¨¨¨" t g´1 " 1, N i " 2 i . The mixed radix representation of t is of the form t " ř g´1 i"0 b i¨Ni , where b i ď t i . Note that under this setup since b i ď t i , the sequence pb 0 , b 1 , . . . , b g´1 q P rrt 0`1 ssˆrrt 1`1 ssˆ¨¨¨ˆrrt g´1`1 ss provides a unique representation and is invertible provided that pt 0 , t 1 , . . . , t g´1 q is given. In other words, given the number t we can uniquely determine the i-th digit in the pt 0 , t 1 , . . . , t g´1 q mixed radix representation for t, which is b i . Furthermore, as a result of Claim 8, we know that t ď 2 β´1 " m.

We are now ready to proceed with the proof. Suppose that pG 0 , G 1 , . . . , G g´1 q is a β-minimal group. We will prove the result by induction and we will show the inductive step (since the base case follows from similar ideas).

For the inductive step, assume the statement holds when the group size is at most 2 α 1 and consider the setup where the group size is 2 α " 2 α 1`1 . Note that we have pt 0 , t 1 , . . . , t g´1 q-infected groups G 0 , G 1 , . . . , G g´1 each of size 2 α 1`1 . We form our super-pool as follows. As before, for each i P rrgss, we select a subset Q i Ă G i of size |Q i | " 2 α 1 . For each individual in Q i we add N i samples into the superpool, where N i is as defined in the previous paragraphs.

Let t be the output of testing the resulting super-pool according to (10) and let b i denote the i-th symbol of the pt 0 , t 1 , . . . , t g´1 qmixed radix representation of t.

Note that based on t, we can determine the number of infected individuals in each of the subgroups Q 0 , G 0 zQ 0 , . . . , Q g´1 , G g´1 zQ g´1 . In particular, since we know t i , and given the output b i which can be recovered after testing the super-pool, we know that for all i P rrgss, the number of infected subjects in Q i is b i and the number of infected subjects in G i zQ i is t i´bi . Given this information, we can generate G 1 0 , G 1 1 , . . . , G 1 g 1´1 , where for i P rrgss, G 1 i Ď Q i or G 1 i Ď G i zQ i , such that the collection is a β-minimal group. Thus, we can apply the inductive hypothesis to G. This establishes that we can identify β infected individuals using at most α tests and completes the proof.

Next, we consider the case d ă β, and show that there exists an ASQGT scheme which requires roughly d β´logpβq¨p αl ogpβqq`d tests. Recall that the main idea behind the parallel search procedure was to simultaneously run a binary search on g subpools each of size 2 α . In this manner, using α tests we can identify β infected. For d ă β, there are not sufficiently many infected individuals to use this method, and so for this setup, rather than perform a binary search in parallel, we test roughly 2 β´logpβq (significantly smaller) subpools at the same time. We refer to this procedure as deep search.

Before proving a relevant lemma, we begin by describing a variant of well-known Newton identities. For completeness, we include a proof. Claim 9. Let S " tj 1 , . . . , j d u P Z be a multiset of nonnegative integers each of which has value at most p´1, where p is an odd prime. Define p pSq " ř d k"1 j k mod p, the th power sum of S over the finite field F p . Then, one can recover S giveǹ p 0 pSq, p 1 pSq, . . . , p d pSq˘.

Proof: We represent S using S p`q , containing the positive elements in S and z P Z, which denotes the number of zeros in S. Given S p`q and z, the set S is uniquely determined.

First, note that Newton's identities can be used to recover the set S p`q " i 1 , i 2 , . . . , i d 1 (

. To see this, let σpi 1 , i 2 , . . . , i d 1 q " ś d 1 k"1 p1´i k xq " ř d 1 k"0 σ k x k P F p rxs and assume that the operations are over the polynomial ring F p rxs, where the elements in S are assumed to lie in F p . Then, we have Figure 14 : Intuitive illustration of the parallel search ASQGT procedure with some details removed for the ease of exposure. In this example, m " 7 and exactly one individual is infectious in each of the three groups. The weights of samples in each test round are set to 4, 2, 1 as seen in Frame 1. A binary search procedure is implemented to find the infected individual in each group. In Frame 1, the test outcome for the first round is 2, implying that there is one infected individual in the second group. Thus, the subgroups from groups 1 and 3 that were probed in Frame 1 are discarded as illustrated in Frame 2.

Similarly, the second subgroup of group 2 that was not tested is discarded as well. The subgroups that contain an infected individual are further probed as seen in Frames 2, 3 and 4.

which implies d ÿ "1 p ¨pS p`q q¨x ¨σpi 1 , . . . , i d 1 q pmod x d`1 q "´x¨σ 1 pi 1 , . . . , i d 1 q.

The above equality in turn implies ř ´1 k"0 σ k¨p ´k pSq "´ ¨σ . Thus, given p pSq, P rds, one can recover σpS p`q q as well as the multiset S p`q . The multiset S can be subsequently recovered by noting that the number of zeros in S equals p 0 pSq´|S p`q |.

Lemma 10. Let p be an odd prime such that p ě 2 L´1 and pp´1q¨d ă 2 β . Suppose that G is a d-infected set of size 2 α , and d ď p´1. Then we can identify the d infected individuals using at most d¨α L tests.

Proof: For simplicity we assume that L|α, and, similar to Lemmas 6 and 7, use induction in α. For the case α " L, we run d tests, and for each test we design a different test group. For P rds, test group contains j P F p samples from each individual indexed by j P rr2 L ss. Suppose that D is a multi-set of elements from rr2 L ss and that D is such that if group j has k infected individuals, then the elements from group j appear k times in D. Then according to the above setup the output of performing the SQGT on pool results in the following -th power sum:

Note that j k ă p (since by design j P F p ) and so p i pj 1 , j 2 , . . . , j d q ď pp´1qd ă 2 β . Thus, for P rrd`1ss, we can recover p pj 1 , j 2 , . . . , j d q " p pj 1 , j 2 , . . . , j d q mod p, since p 0 pj 1 , j 2 , . . . , j d q mod p " d follows from the fact that G is a d-infected set. From the set of d`1 power sums over the field F p , we can recover the multi-set tj 1 , . . . , j d u from Claim 9, which completes the proof of the base case.

For the inductive step, assume the statement holds for group sizes at most 2 α 1 and consider a group size 2 α " 2 α 1`L . As in the proofs of Lemmas 6 and 7, we work with subgroups. The subgroups are formed by partitioning the set of 2 α 1`L individuals into 2 L subgroups P 1 , P 2 , . . . , P 2 L each of size 2 α 1 . Applying the same ideas as before, we form d test groups where test group P rds contains j P F p samples from each individual in subgroup j P rr2 L ss.

Let D " tj 1 1 , j 1 2 , . . . , j 1 d u be a multiset of integers such that j 1 u appears t times in the multiset if and only if group j 1 u has t infected individuals. Using the same approach as for the base case, we first recover the power sums p i pj 1 1 , j 1 2 , . . . , j 1 d q. Then from Claim 9, we recover the set D in the same manner as before and we apply the inductive hypothesis to the subgroups in D. This completes the inductive step and the proof.

Remark 11. For the case d " 1, the deep search procedure coincides with the approach described in Example 5. Deep search may be of limited practical value due to the large amounts of sample material required for testing, but is of theoretical relevance due to the fact that it generalizes Hwang's generalized splitting method to the SQGT setting for a small number of infected individuals.

C. pn, dq-ASQGT schemes

As discussed in the text following Example 5, our general approach to adaptive SQGT is to first partition the set of n individuals into d β subpools and test each subpool separately using either parallel search or deep search, depending on the number of infected in each subpool. Parallel search produces the best results in the worst case, provided that the number of infected individuals across all the subpools is ď β, while parallel search gives the best results for the case of a large number of infected individuals.

Let T P pn, dq denote the number of tests required by our ASQGT scheme, summarized in Algorithm 1, and let n´d " 2 α¨d`2α¨δ`∆ , where α, δ, ∆ are integers such that δ ă d and ∆ ă 2 α . In order to simplify the notation by avoiding floor and ceiling functions, we assume that β|d and β|δ.

Theorem 12. T P pn, dq ď d β¨p α`3`log βq`δ β . Proof: Since the first step involves testing d β`δ β groups, the first step requires d β`δ β tests. For the next steps, note that each group has size ď 2 α`1 β. Hence, we can uncover β infected individuals using at most α`1`logpβq β tests according to Lemmas 6 and 7. In step 3), we use one additional test for every β infected individuals. Since there are d infected the total number of tests required by Algorithm 1 equals

Algorithm 1 Parallel search ASQGT scheme 1) Initialize: Partition the set of n individuals into d`δ β groups, denoted by G 0 , G 1 , . . . , G d`δ

, each of size ď β¨2 α`1 .

Test each subgroup individually. For i P rr d`δ β ss, suppose that G i is a t i -infected group and let D denote the total number of infected subjects across all groups. 2) Parallel Search: Identify a β-minimal group pG i 0 , . . . , G i g´1 q, and apply parallel search on the group to uncover β infected individuals. Remove the β infected individuals from their respective groups. 3) Update: Use one additional test to determine the number of infected subjects in pG i 0 , . . . , G i g´1 q after Step 2). Update t i 0 , . . . , t i g´1 and D. If D ą 0, go to Step 2).

As discussed earlier, the parallel search ASQGT scheme requires Op d β q more tests than the information-theoretic lower bound. When β " 1, our scheme requires Opdq additional tests which agrees with the traditional adaptive binary setting studied in [49] .

Next, we consider the second approach to the ASQGT problem based on deep search, for the case where d ă β. Let T D pn, dq denote the number of tests required by our algorithm and, with a slight abuse of parameter definitions, assume that n´d " 2 α¨d . Furthermore, assume as before that d|2 β and d|n. The corresponding approach is described in Algorithm 2. Proof: The first step in Algorithm 2 requires d ă β tests. According to Lemma 10,  Step 2) requires at most t i¨α β´logpβq´1 tests. Hence, the total number of tests is upper bounded as

D. Error-resilient pn, dq-ASQGT schemes

We consider next the question of designing ASQGT models that can tolerate a bounded number of birth-death (BD) chain errors. Recall from (10) that in the event that there are no errors, the output of testing a pool of individuals, of which d are infected, is an integer t, such that t " d for d ď m and t " m, whenever d ą m. Suppose instead that the erroneous output of testing a pool is t 1 , where t 1 P tt´1, t`1u with the appropriate boundary conditions. We refer to such an error as a single BD error.

Our main result is described in Theorem 17. We prove that there exists a scheme that requires d β´2¨p α`3`log βq`δ β tests that can correct an arbitrary number of test errors. For the case where the number of test errors is a small integer e, d β`e¯¨p α`3`log βq`2¨d β`δ β`e tests suffice, which implies that only e pα`3`log βq`2 d β`e additional tests are required to correct e errors in Algorithm 1.

The next claim highlights one of the main ideas behind our approach: Take multiple copies of samples from each of the individuals being tested in such a way to get error-free readouts even when errors occur. Here, as before, we assume that 2 β " m`1.

Claim 14. Let P be a pool of individuals and suppose that P pˆ3q is a pool which contains three samples from each individual in P. Let t be the output of the test performed on the pool P pˆ3q given that no errors occur, and suppose t 1 is a possibly erroneous output of the test performed on the pool P pˆ3q . Given t 1 , one can determine t.

Proof: Since we have taken 3 samples from each of the individuals in the pool P, it follows that t pmod3q " 0. Thus, if an error occurs, the output of the test under the BD model equals t 1 P tt`1, t´1u which implies that t 1 pmod3q "˘1. If t 1 mod 3 " 1, then t 1 " t`1 and so we can recover t by simply decrementing t 1 by one. Similarly, if t 1 mod 3 "´1, then t 1 " t´1 and we can recover t by incrementing t 1 by one.

Using the idea from the previous claim, we can determine exactly how many infected individuals are present in each of the tested pools despite the fact that testing errors can occur. We describe the underlying method through an example, for which we need the following terminology.

We say that P i is a t i -infected group if the output of testing P pˆ3q i is in the set t3t i´1 , 3t i , 3t i`1 u. We also say that pP i 0 , . . . , P i g´1 q is a β-minimal group if t 0 ě t i 1 쨨¨ě t i g´1 , ř g´2 j"0 t j ă β, but ř g´1 j"0 t j ě β. Example 15. For simplicity, assume that we have m " 3 p2 γ´1 q thresholds, and suppose that pP 0 , P 1 , . . . , P g´1q is a γ-minimal group, where we again make a simplifying assumption, namely γ " g. We proceed in the same manner as described in Lemma 6 and we first form a super-pool, denoted P which consists of 2 i copies of each sample in P i . Afterward, we generate a larger pool of samples, P pˆ3q which contains 3 copies of each sample in P.

Notice that given the output of the test P p3q , we can uniquely determine the number of infected that are in each of the groups P 0 , P 1 , . . . , P g´1 . Suppose that t 1 is the output of testing P p3q and suppose t is the output of testing P p3q assuming no errors occur during testing. From Claim 14, we can recover t and from Lemma 6 it is possible to determine how many infected are in P 0 , how many infected are in P 1 , etc.

Another simple way to see how the above scheme overcomes BD noise is to see that it suffices that test outcomes differ from one another by at least three. This can be easily accomplished by fixing the coefficients of 2 1 and 2 0 in the binary representation of the test outcomes to zero.

More precisely, we can artificially introduce two subgroups, so that when m " 2 γ´1 , we collect samples from subgroups labeled by 1 ă i ă γ, 2 i with the amounts dictated by their labels. If the observed test outcome is t 1 " ř γ´1

i"0ē i¨2 i , then the true test outcome is decoded as:

e γ´1 e γ´2 . . . e 2 e 1 e 0 " #ē γ´1ēγ´2 . . .ē 2 00, ifē 1ē0 " 00 orē 1ē0 " 01, e γ´1ēγ´2 . . .ē 2ē1ē0`1 (binary addition), ifē 1ē0 " 11.

l

The following claim is straightforward.

Claim 16. Let α, β ě 2, g be positive integers where 2 β " m`1, g ď β´2. Suppose that pG 0 , G 1 , . . . , G g´1 q is a pβ´2qminimal group and that each group has size at most 2 α . Then we can identify β´2 infected individuals using at most α tests.

Proof: The proof follows immediately by applying the procedure described in Example 15 and noting that 3¨2 β´2 ă 2 β´1 when β ě 2.

Next, we turn our attention to a scheme designed for a small number of testing errors e. To this end, let T N pn, d, eq denote the number of tests required for a noisy ASQGT scheme that tolerates up to e BD testing errors (see Algorithm 3) . As before, let n´d " 2 α d`2 α δ`∆, where α, δ and ∆ are integers such that δ ă d and ∆ ă 2 α . Once again we assume that β|d and β|δ.

Algorithm 3 Noisy search ASQGT scheme 1) Initialize: Partition the set of samples from the n individuals into d`δ β groups, denoted by P 0 , P 1 , . . . , P d`δ

, and each of size at most β2 α`1 . Test each subgroup P pˆ3q i individually. For i P rr d`δ β ss, suppose that P i is a t i -infected group and let D denote the total number of infected subjects in all subgroups. 2) Parallel Search: Identify a β-minimal group pP i 0 , . . . , P i g´1 q, and apply parallel search to uncover β potential infected subjects. Divide the set of β potentially infected individuals into two groups of sizes t We prove the correctness of our algorithm in the following theorem.

Theorem 17. Let β ě 2. We have

α`3`log βq`δ β˙. Proof: The second term under the minimum follows immediately from the parallel search ASQGT scheme given the use of a robust parallel search. Therefore, in the remainder of the proof, we focus our attention on the first term.

The first step of our algorithm requires d`δ β tests and each time we execute

Step 2), we perform α`1`log β tests. Since

Step 2) is executed at most d β`e times this implies that the total number of tests required by the first two steps of our procedure is at most d`δ β`ˆd β`e˙¨p α`1`log βq .

Step 3), note that since max ! |D 

We consider the following extension of the approach discussed in Example 5. Suppose we have a pool of size 2 α that contains at least one infected subject. We start by testing this pool to determine the total number of infected individuals. There are two cases to consider: (a) The output of the test is 2 or 3, which indicates that there is more than a single infected in the pool or (b) The output of the test is 1.

Suppose that the outcome is (b). In this case, we run a variant of deep search. In particular, we divide the pool into 4 subpools and form a superpool from these 4 subpools which contains 0 samples from the first pool, 1 sample from the second pool, 2 samples from the third pool, and 4 samples from the fourth pool. It is straightforward to verify that in this case we can determine which of the 4 subpools contain the single infected sample by testing the superpool, and we then repeat this procedure using the subpool which contains the single infected.

If the outcome is (a), then we proceed to divide the pool of size 2 α into two disjoint subpools, each of size 2 α´1 . We further select one of the two subpools for testing. If the subpool tested contains a single infected, then we continue by applying the procedure discussed in the previous paragraph on the subpool of size 2 α´1 that contains one infected sample. Otherwise, we repeat the procedure from this paragraph on one of the subpools of size 2 α´1 that contains more than a single infected subject.

Using the procedure described above, it is straightforward to verify that recovering 2 infected individuals requires at most α tests provided we know the number of infected samples in the pool of size 2 α . Now suppose n " d 2 α . Then we can recover d infected subjects using at most 2¨d`d¨α 2 tests as follows. First, we partition the set of n individuals into d groups each of size 2 α and we initially test each of these d groups. Afterward, we search for the infected individuals using the process outlined in this example. l

We note that despite the fact that we have focused on the case where m is a power of two, the next example shows that in some cases our ideas extend to settings where m is not necessarily a power of two. In the next example, we show an adaptive scheme that requires at most roughly d`d¨`log 3 p n d q`1˘. The ideas are similar to the previous example except that here we only allow 3 thresholds.

Example 19. For this example, we assume that n " d¨3 α . The output of the test is t, where: The core idea behind the testing strategy is a simple extension of the previous example. Suppose we have a pool of size 3 α that contains at least one infected individual. First, we test this pool of size 3 α to determine the total number of infected individuals. There are two cases to consider: (a) The output of the test equals 2, which indicates that there is more than one infected sample in the pool or (b) The output of the test equals 1.

Suppose (b) occurred. We perform the same procedure as before except that instead of dividing the pool into 4 subpools, we divide the pool into 3 subpools of equal size. Next, we form a superpool from these 3 sub pools which contains 0 samples from the first pool, 1 sample from the second pool, and 2 samples from the third pool. Similarly as before, we can determine which of the three subpools contains the single infected sample, and we then repeat this procedure using the subpool which contains the single infected sample.

If (a) occurs, then we perform the same procedure as in the previous example. In particular, we divide the pool of size 3 α into two disjoint subpools each of size at most r 3 α 2 s and perform a single test. If two infected individuals are contained in a single pool, then we repeat the procedure from this paragraph on the pool of size at most r 3 α 2 s that contains at least two infected samples. Otherwise, we perform the procedure from the previous paragraph on the subpool of size at most r 3 α 2 s that contains a single infected sample.

Using this approach, it is straightforward to verify that recovering an infected requires at most α`1 tests. Thus we can recover d infected individuals using at most d`d¨pα`1q tests as follows. First, we partition the set of n infected into d groups each of size 3 α . Afterward, we search for the infected individuals using the process outlined in this example. l

Since the model proposed in the previous example is identical to the one used for probabilistic priors and described in Section IV, we now directly compare the two in terms of the number of tests required per individual. Recall that the model in section IV required on average 1 s`p¨p 1´pq s´1¨r log ss`1´p1´pq s´s¨p¨p 1´pq s´1 (14) tests per individual where s represents the size of each subpool used in the first step of the corresponding algorithm. For n large enough, our setup requires approximately p`p¨log 3ˆ1 p˙ ( 15) tests where p " d n . Figure 15 compares the number of tests required in (14) and (15) . Notice that the ASQGT scheme from the previous example requires only roughly half the tests per individual of the approach from Section IV. However, the latter 25 method is simpler to implement in practice since it only requires two stages of testing. We also note that since the schemes are not exclusive, it is possible to use a combination of both approaches if needed. (14) and (15) . The choice of s is optimized for each value of p for the probabilistic priors setting.

As mentioned previously, in order to formulate effective and optimal testing schemes, the underlying community network structure must be incorporated. Towards that end, we assume that the community labels are known as well as their sizes (not the entire network, but entities like families or clusters of families in close proximity; this assumption is realistic, as most testing sites require subjects to submit their addresses). The aim is to find efficient strategies that will identify communities with high infection rates, rather than infected individuals, as this would guide effective quarantine strategies.

More precisely, consider a partition of a population of N individuals into communities A 1 , A 2 , . . . , A f of size N 1 , N 2 , ..., N f , respectively, where N " N 1`. ..`N f and f ě 2. Each group has some (unknown) number of infected individuals equal to d i , i " 1, . . . , s, and d "

The following question is of interest: Devise adaptive and nonadaptive GT and SQGT schemes that identify heavy hitter communities, i.e., communities with at least d{k infected individuals, where k is an input parameter.

The naive nonadaptive scheme for this problem corresponds to running within each of the f communities an optimal testing scheme for determining the number of infected individuals. Each such scheme requires Θplog N i q tests [71] , leading to a total of Θp ř f i"1 log N i q tests. Note that Θplog Nq tests are both necessary and sufficient to estimate the number of defectives in general, but it is conceivable that a better result is possible when we already know an upper bound on this number, which is the case here. This approach is suboptimal, and we describe an alternative nonadaptive binary testing scheme for the heavy hitters problem that requires significantly fewer tests when the total number of infected individuals, d, is much smaller than the population size n. We leave as an important open problem to construct semiquantitative testing schemes for the heavy hitters problem with few adaptivity stages and requiring significantly fewer tests than the scheme we propose below.

First, we note that the heavy hitters problem can be solved with t " Opk log f q queries that on input a set T Ď r f s output ř iPT d i [45] , which corresponds to the quantitive GT model. Indeed, this corresponds to the setting of compressed sensing with 0/1 linear tests. We show below how to emulate such a query with error probability using r " Op2 2d¨l ogp1{ qq randomized disjunctive queries. Combining the two observations above immediately yields a nonadaptive group testing scheme using r¨t " Opk¨log f¨2 2d¨l ogp1{ qq tests that solves the heavy hitters problem with error probability at most t¨ via a union bound. For example, if d ă log log log N and ď 1 t log n then the required number of tests may be significantly smaller than that required by the naive scheme from the previous paragraph.

It remains to show how to emulate the query ř iPT d i with error probability using r tests. Consider a randomized test obtained by independently including each individual j P Ť iPT A i in the test with probability 1{2, and let Y denote the test output. Then, we have PrrY " 0s " ś iPT 2´d i " 2´ř iPT d i , since the test outputs 0 if and only if no infected individual is included. Noting that ř iPT d i ď d, a Chernoff bound guarantees that we can determine ř iPT d i with error probability at most by independently sampling r " Op2 2d logp1{ qq such tests Y 1 , Y 2 , . . . , Y r and setting our estimate to be Q´l og´1 r ř r a"1 Y a¯] , where rxu denotes the closest integer to x. This yields the desired result.

We conclude the discussion with the following remarks: 1) The above scheme provides a reduction from community-aware testing of heavy hitters to the standard heavy hitters problem in compressed sensing. While this provides a proof of concept, it remains to be seen whether a direct approach can provide more effective test designs for the identification of heavy hitter communities via disjunctive queries. 2) An important direction is to construct an analogous approach for the detection of heavy hitter communities using SQGT schemes. Recall that quantitative group testing (equivalently, the compressed sensing model via binary matrices) is an extremal special case of SQGT, whereas standard group testing is another extreme. It is therefore natural to expect that SQGT provides the identification of heavy hitter communities at varying efficiency depending on the granularity of the quantization levels. 3) Furthermore, we ask whether adaptivity can help to identify heavy hitter communities more efficiently than nonadaptive schemes can offer.

A number of works have focused on RT-PCR asymmetric error models that assume that positive samples can actually test negative while the opposite scenario is highly unlikely [29] . As already pointed out, these assumptions are not practically justified since even as few as 10 viral cDNA fragments can lead to detectable fluorescence levels after roughly 40 cycles of amplification. Hence, the cause of false negative measurements does not lie in inadequate PCR testing but erroneous sample collection instead, in addition to possible mutations in the genomic regions used as primers. In both cases, no matter how many times an RT-PCR test is repeated, an infected sample may not be identified (i.e., the sample is masked). As an example, the CDC originally identified three pairs of primers from the N open reading frame (gene) of the SARS-CoV-2 virus for testing, but since one pair was removed due to the presence of mutations in a larger-than-acceptable population. There are further efforts to reduce the problem of false negatives due to mutations such as using primers from at least two genes [72] .

The problem of mutations in primer regions of individuals tested via RT-PCR is of relevance to GT both from the perspective of measurement modeling (as mutations add an additional level of nonlinearity to the measurements that are not captured by current approaches) as well as error analysis. It is important to observe that mutations or undesired hybridization to nontarget regions may lead to variable test outcomes for the same sample in different tests. As a result, trying to exactly estimate the viral load of the individuals as proposed in [25] is not possible and estimates like the ones used in the SQGT framework may be more appropriate. Furthermore, quantization noise is signal-dependent, which is another desirable feature of the SQGT framework.

To examine the influence of mutations on RT-PCR we examined the GISAID [41] database of Cov-SARS-2 genomes and identified 7 individuals with mutations in the N1 and N2 primer regions. Using the FastPCR online simulation software [73] , we examined the influence of the mutation on primer binding and PCR amplification. The results are summarized in Table I . Furthermore, the complete primer and DNA sequences are given in Appendix A. There, the symbols 'f' and 'r' refer to the DNA strands' forward and reverse directions, respectively. In the forward direction, the genome and primer have to be an exact match, while in the reverse direction the two strings have to be Watson-Crick complementary. As one can observe, mutations along the forward (reverse) direction of the N1 or N2 regions that do not contain the exact match (or Watson-Crick complement) can severely affect the efficiency of primer/target bonding. For a more precise characterization, the corresponding melting temperatures are given in the Table I along with an estimate of the primer binding efficiency for the N1 and N2 regions.

As seen in the results of the simulation, not all samples that have mutations along the primer region are amplified.

We provided an in-depth description of the quantitative RT-PCR protocol suitable for nonexperts, an overview of existing GT testing protocols for Covid-19 and their practical implications. These comparative studies motivated further explorations of quantized GT (or semiquantitative GT (SQGT)) protocols, especially under a new measurement-error model termed the birth-death chain noise model. We furthermore developed state-of-the-art adaptive SQGT schemes with probabilistic and combinatorial priors and provided extensive analytical results, including performance bounds, algorithmic solutions, and noisy testing protocols. We also designed a probabilistic setting protocol which is extremely simple to implement by nonexperts and capable to handle heavy hitters.

Many open problems remain, including:

‚ Probabilistic testing schemes for more than 3 thresholds: In Section IV, we considered the setup where each test generated the output 0, 1, or 2 depending upon the number of defectives in each group. How much can one reduce the number of tests of our schemes if we incorporate additional semi-quantitative information, in the presence of errors? ‚ Worst-case general SQGT testing schemes with a constant number of rounds: The schemes described in Section V have the potential drawback that almost every test depends upon the results of prior tests. It has been shown that in the binary group testing setting, the information-theoretic lower bound can be achieved using only two rounds of nonadaptive testing when the number of infected individuals is at most n c for any constant c ă 1 [74] . In a very recent line of work, we showed how to implement two-round SQGT schemes for the saturation model studied in Section V. It remains an open problem to generalize the approach for general quantized GT paradigms. ‚ Practical SQGT schemes resilient to errors: Our practical two-stage SQGT schemes from Section IV-A can be enhanced with noise-resilience properties in a straightforward by repeating each test a prescribed number of times, while keeping the number of testing stages the same. Nevertheless, it would be interesting to find more efficient, and still practical, ways of adding good noise-resilience properties to these schemes. ‚ Community-Aware Testing: Section VI presented a simple approach to the problem of heavy-hitter community identification for classical GT. No results on this problem are currently available for general SQGT methods.

Coronavirus Pandemic (COVID-19)

Here's how COVID-19 compares to past outbreaks

Testing the key to reopening economy, returning life to normal, officials say

New drool-based tests are replacing the dreaded coronavirus nasal swab

Nebraska public health lab begins pool testing COVID-19 samples

The detection of defective members of large populations

Group testing: An information theory perspective

Assessment of specimen pooling to conserve SARS CoV-2 testing resources

A note on double pooling tests

Optimal group testing to exit the Covid confinement

Group testing against COVID-19

Boosting test-efficiency by pooled testing strategies for SARS-CoV-2

On accelerated testing for COVID-19 using group testing

Rapid, large-scale, and effective detection of COVID-19 via non-adaptive testing

Efficient high throughput SARS-CoV-2 testing to detect asymptomatic carriers

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

Noisy pooled PCR for virus testing

Does Covid-19 Hit Women and Men Differently? U.S. Isn't Keeping Track

Covid-19's devastating toll on black and Latino Americans, in one chart

CDC 2019-novel coronavirus (2019-nCoV) real-time RT-PCR diagnostic panel

Efficiency of the polymerase chain reaction

How fast does the SARS-Cov-2 virus really mutate in heterogeneous populations?" medRxiv

Low-cost and high-throughput testing of COVID-19 viruses and antibodies via compressed sensing: System concepts and computational experiments

Efficient noise-blind 1 -regression of nonnegative compressible signals

Tapestry: A single-round smart pooling technique for COVID-19 testing

Efficient high-throughput SARS-CoV-2 testing to detect asymptomatic carriers

Rethinking covid-19 test sensitivity -a strategy for containment

SARS-CoV2 Testing: The limit of detection matters

Community aware group testing

Semiquantitative group testing

Group testing for non-uniformly quantized adder channels

Code construction and decoding algorithms for semi-quantitative group testing with nonuniform thresholds

A generalized binomial group testing problem

Poisson group testing: A probabilistic model for nonadaptive streaming boolean compressed sensing

Born again group testing: Multiaccess communications

Determining subsets by unramified experiments

Generalized superimposed codes and their application to random multiple access

GISAID: Global initiative on sharing all influenza data-from vision to reality

What are the differences between PCR

Real-time PCR quantification using a variable reaction efficiency model

GISAID

Potency and timing of antiviral therapy as determinants of duration of SARS CoV-2 shedding and intensity of inflammatory response

Viral dynamics in mild and severe cases of COVID-19

On-campus COVID-19 testing

Sketching via hashing: from heavy hitters to compressed sensing to sparse Fourier transform

Bounds on the length of disjunctive codes

Explicit non-adaptive combinatorial group testing schemes

An efficient algorithm for capacity-approaching noisy adaptive group testing

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

Threshold group testing

Improved constructions for non-adaptive threshold group testing

Information theoretic bounds for compressed sensing

Compressive sensing

Greed is good: Algorithmic results for sparse approximation

Subspace pursuit for compressive sensing signal reconstruction

A compressed sensing approach to group-testing for COVID-19 detection

Compressive sensing DNA microarrays

A comparative study of quantized compressive sensing schemes

Information theoretical and algorithmic approaches to quantized compressive sensing

Two-stage adaptive pooling with RT-qPCR for COVID-19 screening

Weighted superimposed codes and constrained integer compressed sensing

Graph-constrained group testing

Adaptive group testing on networks with community structure

Group testing for overlapping communities

Positively correlated samples save pooled testing costs

Group testing for consecutive positives

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

Correlation inequalities on some partially ordered sets

Combinatorial group testing and its applications

Semiquantitative group testing in at most two rounds

Bounds for nonadaptive group tests to estimate the amount of defectives

Optimization of primer sets and detection protocols for SARS-CoV-2 of coronavirus disease 2019 (COVID-19) using PCR and real-time PCR

Optimal adaptive group testing

The authors are grateful to Sergei Maslov and Nigel Goldenfeld from the University of Illinois for several insightful discussions.

We present below the results of the PCR simulation run on DNA sequences that contain mutations along the N1 and N2 regions of the genome. The notation EPI ISL xxxxxx corresponds to the sample ID. As already indicated, the symbols 'f' and 'r' at the end of the primer regions indicate the DNA strand directions, forward and reverse respectively. The symbol 'Y' indicates a successful PCR amplification, while the symbol 'N' indicates that PCR amplification cannot be initiated. We also list the percentage of the primer string that is matched by genomic DNA, and the melting temperature T m . EPI ISL 413609 N1f 5 -g a c c c c a a a a t c a g c g a a a t Y 100% T m =51.6˝C | | | | | | | | | | | | | | | | | | | | t g g a c c c c a a a a t c a g c g a a a t g c a c N1r g t c t a a g t t g a c c g t c a t t g g t c t -5 Y 100% T m =56.3˝C | | | | | | | | | | | | | | | | | | | | | | | | c t c a g a t t c a a c t g g c a g t a a c c a g a a t g g N2f 5 -t t a c a a a c a t t g g c c g c a a a Y 100% T m =52.9˝C | | | | | | | | | | | | | | | | | | | | g a t t a c a a a c a t t g g c c g c a a a t t g c N2r a a g a a g c c t t a c a g c g c g -5 Y 97% T m =52.2˝C | | | | | | | | | | | | | | | | | : c g t t c t t c g g a a t g t c g c g t a t t g EPI ISL 415600 N1f 5 -g a c c c c a a a a t c a g c g a a a t Y 100% T m =51.6˝C | | | | | | | | | | | | | | | | | | | | t g g a c c c c a a a a t c a g c g a a a t g c a c N1r 28 g t c t a a g t t g a c c g t c a t t g g t c t -5 N 97% T m =51.7˝C | | | | | | | | | : | | | | | | | | | | | | | | c t c a g a t t c a a t t g g c a g t a a c c a g a a t g g N2f 5 -t t a c a a a c a t t g g c c g c a a a Y 100% T m =52.9˝C | | | | | | | | | | | | | | | | | | | | g a t t a c a a a c a t t g g c c g c a a a t t g c N2r a a g a a g c c t t a c a g c g c g -5 Y 100% T m =54.7˝C | | | | | | | | | | | | | | | | | | c g t t c t t c g g a a t g t c g c g c a t t g EPI ISL 416650 N1f 5 -g a c c c c a a a a t c a g c g a a a t N 97% T m =42.6˝C | | | | | | | | | | | | | : | | | | | | t g g a c c c c a a a a t c a t c g a a a t g c a c N1r g t c t a a g t t g a c c g t c a t t g g t c t -5 Y 100% T m =56.3˝C | | | | | | | | | | | | | | | | | | | | | | | | c t c a g a t t c a a c t g g c a g t a a c c a g a a t g g N2f 5 -t t a c a a a c a t t g g c c g c a a a Y 100% T m =52.9˝C | | | | | | | | | | | | | | | | | | | | g a t t a c a a a c a t t g g c c g c a a a t t g c N2r a a g a a g c c t t a c a g c g c g -5 Y 100% T m =54.7˝C | | | | | | | | | | | | | | | | | | c g t t c t t c g g a a t g t c g c g c a t t g EPI ISL 417938 N1f 5 -g a c c c c a a a a t c a g c g a a a t Y 100% T m =51.6˝C | | | | | | | | | | | | | | | | | | | | t g g a c c c c a a a a t c a g c g a a a t g c a c N1r g t c t a a g t t g a c c g t c a t t g g t c t -5 Y 100% T m =56.3˝C | | | | | | | | | | | | | | | | | | | | | | | | c t c a g a t t c a a c t g g c a g t a a c c a g a a t g g N2f 5 -t t a c a a a c a t t g g c c g c a a a Y 95% T m =47.3˝C a t t a t a a a c a t t g g c c g c a a a t t g c N2r a a g a a g c c t t a c a g c g c g -5 Y 100% T m =54.7˝C | | | | | | | | | | | | | | | | | | c g t t c t t c g g a a t g t c g c g c a t t g EPI ISL 422983 N1f 5 -g a c c c c a a a a t c a g c g a a a t Y 95% T m =44.6˝C g g a a c c c a a a a t c a g c g a a a t g c a c N1r g t c t a a g t t g a c c g t c a t t g g t c t -5 N 95% T m =52.1˝C 29 | | | | | : | | | | | | | | | | | | | | | | | | c t c a g a t a c a a c t g g c a g t a a c c a g a a t g g N2f 5 -t t a c a a a c a t t g g c c g c a a a Y 100% T m =52.9˝C | | | | | | | | | | | | | | | | | | | | g a t t a c a a a c a t t g g c c g c a a a t t g c N2r a a g a a g c c t t a c a g c g c g -5 Y 100% T m =54.7˝C | | | | | | | | | | | | | | | | | | c g t t c t t c g g a a t g t c g c g c a t t g EPI ISL 424955 N1f 5 -g a c c c c a a a a t c a g c g a a a t Y 100% T m =51.6˝C g g a c c c c a a a a t c a g c g a a a t g c a c N1r g t c t a a g t t g a c c g t c a t t g g t c t -5 Y 100% T m =56.3˝C | | | | | | | | | | | | | | | | | | | | | | | | c t c a g a t t c a a c t g g c a g t a a c c a g a a t g g N2f 5 -t t a c a a a c a t t g g c c g c a a a N 97% T m =43.1˝C | | | | | | | | | | | | | | | : | | | | g a t t a c a a a c a t t g g c c t c a a a t t g c N2r a a g a a g c c t t a c a g c g c g -5 Y 100% T m =54.7˝C | | | | | | | | | | | | | | | | | | c g t t c t t c g g a a t g t c g c g c a t t g EPI ISL425148 n1f5 -g a c c c c a a a a t c a g c g a a a t Y 100% T m =51.6˝C | | | | | | | | | | | | | | | | | | | | t g g a c c c c a a a a t c a g c g a a a t g c a c N1r g t c t a a g t t g a c c g t c a t t g g t c t -5 N 97% T m =51.7˝C | | | | | | | | | : | | | | | | | | | | | | | | c t c a g a t t c a a t t g g c a g t a a c c a g a a t g g N2f 5 -t t a c a a a c a t t g g c c g c a a a Y 100% T m =52.9˝C | | | | | | | | | | | | | | | | | | | | g a t t a c a a a c a t t g g c c g c a a a t t g c N2r a a g a a g c c t t a c a g c g c g -5 Y 100% T m =54.7˝C | | | | | | | | | | | | | | | | | | c g t t c t t c g g a a t g t c g c g c a t t g