group testing

Unlike many areas of mathematics, the origins of group testing can be traced back to a single report written by a single person: Robert Dorfman. The motivation arose during the Second World War when the United States Public Health Service and the Selective service embarked upon a large-scale project to weed out all syphilitic men called up for induction. Testing an individual for syphilis involves drawing a blood sample from them and then analysing the sample to determine the presence or absence of syphilis. At the time, performing this test was expensive, and testing every soldier individually would have been very expensive and inefficient.

Supposing there are $n$ soldiers, this method of testing leads to $n$ separate tests. If a large proportion of the people are infected then this method would be reasonable. However, in the more likely case that only a very small proportion of the men are infected, a much more efficient testing scheme can be achieved. The feasibility of a more effective testing scheme hinges on the following property: the soldiers can be pooled into groups, and in each group the blood samples can be combined. The combined sample can then be tested to check if at least one soldier in the group has syphilis. This is the central idea behind group testing. If one or more of the soldiers in this group has syphilis, then a test is wasted (more tests need to be performed to find which soldier(s) it was). On the other hand, if no one in the pool has syphilis then many tests are saved, since every soldier in that group can be eliminated with just one test.

The items that cause a group to test positive are generally called defective items (these are the broken lightbulbs, syphilitic men, etc.). Often, the total number of items is denoted as $n$ and $d$ represents the number of defectives if it is assumed to be known.

There are two independent classifications for group-testing problems; every group-testing problem is either adaptive or non-adaptive, and either probabilistic or combinatorial.

In probabilistic models, the defective items are assumed to follow some probability distribution and the aim is to minimise the expected number of tests needed to identify the defectiveness of every item. On the other hand, with combinatorial group testing, the goal is to minimise the number of tests needed in a 'worst-case scenario' – that is, create a minmax algorithm – and no knowledge of the distribution of defectives is assumed.

The other classification, adaptivity, concerns what information can be used when choosing which items to group into a test. In general, the choice of which items to test can depend on the results of previous tests, as in the above lightbulb problem. An algorithm that proceeds by performing a test, and then using the result (and all past results) to decide which next test to perform, is called adaptive. Conversely, in non-adaptive algorithms, all tests are decided in advance. This idea can be generalised to multistage algorithms, where tests are divided into stages, and every test in the next stage must be decided in advance, with only the knowledge of the results of tests in previous stages.

Although adaptive algorithms offer much more freedom in design, it is known that adaptive group-testing algorithms do not improve upon non-adaptive ones by more than a constant factor in the number of tests required to identify the set of defective items.{{Cite journal

|last1=Atia|first1=George Kamal

|last2=Saligrama|first2=Venkatesh

|date = March 2012

|title = Boolean compressed sensing and noisy group testing

|journal = IEEE Transactions on Information Theory

|volume = 58|issue = 3

|pages = 1880–1901

|arxiv = 0907.1061

|doi = 10.1109/TIT.2011.2178156|s2cid=8946216

}}

{{cite book

|last1=Ding-Zhu|first1= Du

|last2=Hwang|first2=Frank K.

|title=Combinatorial group testing and its applications

|date=1993

|publisher=World Scientific

|location=Singapore

|isbn=978-9810212933}} In addition to this, non-adaptive methods are often useful in practice because one can proceed with successive tests without first analysing the results of all previous tests, allowing for the effective distribution of the testing process.

There are many ways to extend the problem of group testing. One of the most important is called noisy group testing, and deals with a big assumption of the original problem: that testing is error-free. A group-testing problem is called noisy when there is some chance that the result of a group test is erroneous (e.g. comes out positive when the test contained no defectives). The Bernoulli noise model assumes this probability is some constant, $q$, but in general it can depend on the true number of defectives in the test and the number of items tested. For example, the effect of dilution can be modelled by saying a positive result is more likely when there are more defectives (or more defectives as a fraction of the number tested), present in the test.{{cite journal |last1=Hung |first1=M. |last2=Swallow |first2=William H. |title=Robustness of Group Testing in the Estimation of Proportions |journal=Biometrics |date=March 1999 |volume=55 |issue=1 |pages=231–7 |doi=10.1111/j.0006-341X.1999.00231.x|pmid=11318160 |s2cid=23389365 }} A noisy algorithm will always have a non-zero probability of making an error (that is, mislabeling an item).

Group testing can be extended by considering scenarios in which there are more than two possible outcomes of a test. For example, a test may have the outcomes $0,\; 1$ and $2^+$, corresponding to there being no defectives, a single defective, or an unknown number of defectives larger than one. More generally, it is possible to consider the outcome-set of a test to be $\{0,\; 1,\; \backslash ldots\; ,\; k^+\}$ for some $k\; \backslash in\; \backslash mathbb\{N\}$.

Another extension is to consider geometric restrictions on which sets can be tested. The above lightbulb problem is an example of this kind of restriction: only bulbs that appear consecutively can be tested. Similarly, the items may be arranged in a circle, or in general, a net, where the tests are available paths on the graph. Another kind of geometric restriction would be on the maximum number of items that can be tested in a group,{{efn|The original problem that Dorfman studied was of this nature (although he did not account for this), since in practice, only a certain number of blood sera could be pooled before the testing procedure became unreliable. This was the main reason that Dorfman’s procedure was not applied at the time.}} or the group sizes might have to be even and so on. In a similar way, it may be useful to consider the restriction that any given item can only appear in a certain number of tests.

There are endless ways to continue remixing the basic formula of group testing. The following elaborations will give an idea of some of the more exotic variants. In the 'good–mediocre–bad' model, each item is one of 'good', 'mediocre' or 'bad', and the result of a test is the type of the 'worst' item in the group. In threshold group testing, the result of a test is positive if the number of defective items in the group is greater than some threshold value or proportion.{{cite journal

|last1 = Chen|first1 = Hong-Bin

|last2 = Fu|first2 = Hung-Lin

|date = April 2009

|title = Nonadaptive algorithms for threshold group testing

|journal = Discrete Applied Mathematics

|volume = 157|issue = 7

|pages = 1581–1585

|doi = 10.1016/j.dam.2008.06.003

|doi-access = free

}}

Group testing with inhibitors is a variant with applications in molecular biology. Here, there is a third class of items called inhibitors, and the result of a test is positive if it contains at least one defective and no inhibitors.{{cite journal

|last1 = De Bonis|first1= Annalisa

|date = 20 July 2007

|title = New combinatorial structures with applications to efficient group testing with inhibitors

|journal = Journal of Combinatorial Optimization

|volume=15|issue=1

|pages = 77–94

|doi = 10.1007/s10878-007-9085-1|s2cid= 207188798

}}

The concept of group testing was first introduced by Robert Dorfman in 1943 in a short report{{citation

|last1=Dorfman|first1=Robert

|title=The Detection of Defective Members of Large Populations

|journal=The Annals of Mathematical Statistics

|date=December 1943

|volume=14|issue=4

|pages=436–440

|jstor=2235930

|doi=10.1214/aoms/1177731363|doi-access=free

}} published in the Notes section of Annals of Mathematical Statistics.{{efn|However, as is often the case in mathematics, group testing has been subsequently re-invented multiple times since then, often in the context of applications. For example, Hayes independently came up with the idea to query groups of users in the context of multiaccess communication protocols in 1978.{{cite journal

|last1 = Hayes|first1=J.

|date = August 1978

|title = An adaptive technique for local distribution

|journal = IEEE Transactions on Communications

|volume = 26|issue = 8

|pages = 1178–86

|doi = 10.1109/TCOM.1978.1094204

}}}} Dorfman's report – as with all the early work on group testing – focused on the probabilistic problem, and aimed to use the novel idea of group testing to reduce the expected number of tests needed to weed out all syphilitic men in a given pool of soldiers. The method was simple: put the soldiers into groups of a given size, and use individual testing (testing items in groups of size one) on the positive groups to find which were infected. Dorfman tabulated the optimum group sizes for this strategy against the prevalence rate of defectiveness in the population.

Stephen Samuels

{{cite journal

|last1 = Samuels|first1 = Stephen

|date =1978

|title = The Exact Solution to the Two-Stage Group-Testing Problem

|journal =Technometrics

|volume = 20|issue =4

|pages = 497–500

|doi = 10.1080/00401706.1978.10489706|doi-access = free

}}

found a closed-form solution for the optimal group size as a function of the prevalence rate.

After 1943, group testing remained largely untouched for a number of years. Then in 1957, Sterrett produced an improvement on Dorfman's procedure.{{cite journal

|last1 = Sterrett|first1 = Andrew

|date = December 1957

|title = On the detection of defective members of large populations

|journal = The Annals of Mathematical Statistics

|volume = 28|issue = 4

|pages = 1033–6

|doi = 10.1214/aoms/1177706807|doi-access = free

}} This newer process starts by again performing individual testing on the positive groups, but stopping as soon as a defective is identified. Then, the remaining items in the group are tested together, since it is very likely that none of them are defective.

The first thorough treatment of group testing was given by Sobel and Groll in their formative 1959 paper on the subject.{{cite journal

|last1 = Sobel|first1 = Milton

|last2 = Groll|first2 = Phyllis A.

|date = September 1959

|title = Group testing to eliminate efficiently all defectives in a binomial sample

|journal = Bell System Technical Journal

|volume = 38|issue = 5

|pages = 1179–1252

|doi = 10.1002/j.1538-7305.1959.tb03914.x}} They described five new procedures – in addition to generalisations for when the prevalence rate is unknown – and for the optimal one, they provided an explicit formula for the expected number of tests it would use. The paper also made the connection between group testing and information theory for the first time, as well as discussing several generalisations of the group-testing problem and providing some new applications of the theory.

The fundamental result by Peter Ungar in 1960 shows that if the prevalence rate $p>p\_\{u\}=(3-\backslash sqrt\{5\})/2\backslash approx\; 0.38$, then individual testing is the optimal group testing procedure with respect to the expected number of tests, and if

|last1 = Ungar|first1 = Peter

|date =February 1960

|title = Cutoff points in group testing

|journal = Communications on Pure and Applied Mathematics

|volume = 13|issue = 1

|pages = 49–54

|doi = 10.1002/cpa.3160130105|doi-access = free

}}

Group testing was first studied in the combinatorial context by Li in 1962,{{cite journal

|last1=Li|first1=Chou Hsiung

|date = June 1962

|title = A sequential method for screening experimental variables

|journal= Journal of the American Statistical Association

|volume = 57|issue = 298

|pages = 455–477

|doi = 10.1080/01621459.1962.10480672}} with the introduction of Li’s $s$-stage algorithm. Li proposed an extension of

Dorfman's '2-stage algorithm' to an arbitrary number of stages that required no more

than $t\; =\; \backslash frac\{e\}\{\backslash log\_2(e)\}d\; \backslash log\_2(n)$ tests to be guaranteed to find $d$ or fewer defectives among $n$ items.

The idea was to remove all the items in negative tests, and divide the remaining items into groups as was done with the initial pool. This was to be done $s\; -\; 1$ times before performing individual testing.

Combinatorial group testing in general was later studied more fully by Katona in 1973.{{cite book

|last1=Katona|first1=Gyula O.H.

|year = 1973

|title = Combinatorial Search Problems

|chapter = A survey of combinatorial theory

|pages = 285–308 |isbn=978-0-7204-2262-7

|publisher = North-Holland}} Katona introduced the matrix representation of non-adaptive group-testing and produced a procedure for finding the defective in the non-adaptive 1-defective case in no more than $t\; =\backslash lceil\; \backslash log\_2(n)\; \backslash rceil$tests, which he also proved to be optimal.

In general, finding optimal algorithms for adaptive combinatorial group testing is difficult, and although the computational complexity of group testing has not been determined, it is suspected to be hard in some complexity class. However, an important breakthrough occurred in 1972, with the introduction of the generalised binary-splitting algorithm. The generalised binary-splitting algorithm works by performing a binary search on groups that test positive, and is a simple algorithm that finds a single defective in no more than the information-lower-bound number of tests.

In scenarios where there are two or more defectives, the generalised binary-splitting algorithm still produces near-optimal results, requiring at most $d\; -\; 1$ tests above the information lower bound where $d$ is the number of defectives. Considerable improvements to this were made in 2013 by Allemann, getting the required number of tests to less than $0.187d\; +\; 0.5\backslash log\_2(d)\; +\; 5.5$ above the information lower bound when $n/d\; \backslash geq\; 38$ and $d\; \backslash geq\; 10$.{{cite book

|last1 = Allemann|first1 = Andreas

|title = Information Theory, Combinatorics, and Search Theory

|chapter = An Efficient Algorithm for Combinatorial Group Testing

|date = 2013

|series = Lecture Notes in Computer Science

|volume = 7777

|pages = 569–596

|doi = 10.1007/978-3-642-36899-8_29

|isbn = 978-3-642-36898-1

}} This was achieved by changing the binary search in the binary-splitting algorithm to a complex set of sub-algorithms with overlapping test groups. As such, the problem of adaptive combinatorial group testing – with a known number or upper bound on the number of defectives – has essentially been solved, with little room for further improvement.

There is an open question as to when individual testing is minmax. Hu, Hwang and Wang showed in 1981 that individual testing is minmax when $n\; \backslash leq\; \backslash lfloor\; (5d\; +\; 1)/2\; \backslash rfloor$, and that it is not minmax when $n\; >\; 3d$.{{cite journal

|last1= Hu|first1 = M. C.

|last2 = Hwang|first2 = F. K.

|last3 = Wang|first3 = Ju Kwei

|date = June 1981

|title = A Boundary Problem for Group Testing

|journal = SIAM Journal on Algebraic and Discrete Methods

|volume = 2|issue = 2

|pages = 81–87

|doi = 10.1137/0602011}} It is currently conjectured that this bound is sharp: that is, individual testing is minmax if and only if $n\; \backslash leq\; 3d$.{{cite journal

|last1 = Leu|first1 = Ming-Guang

|date = 28 October 2008

|title = A note on the Hu–Hwang–Wang conjecture for group testing.

|journal = The ANZIAM Journal

|volume = 49|issue = 4

|page = 561

|doi = 10.1017/S1446181108000175|doi-access = free

}}{{efn|This is sometimes referred to as the Hu-Hwang-Wang conjecture.}} Some progress was made in 2000 by Riccio and Colbourn, who showed that for large $n$, individual testing is minmax when $d\; \backslash geq\; n/\backslash log\_\{3/2\}(3)\; \backslash approx\; 0.369n$.{{cite journal

|last1 = Riccio|first1 = Laura

|last2 = Colbourn|first2 = Charles J.

|date = 1 January 2000

|title = Sharper bounds in adaptive group testing

|journal = Taiwanese Journal of Mathematics

|volume = 4|issue = 4

|pages = 669–673|doi = 10.11650/twjm/1500407300

|doi-access = free

}}

One of the key insights in non-adaptive group testing is that significant gains can be made by eliminating the requirement that the group-testing procedure be certain to succeed (the "combinatorial" problem), but rather permit it to have some low but non-zero probability of mis-labelling each item (the "probabilistic" problem). It is known that as the number of defective items approaches the total number of items, exact combinatorial solutions require significantly more tests than probabilistic solutions — even probabilistic solutions permitting only an asymptotically small probability of error.{{efn|The number of tests, $t$, must scale as $t\; =\; O\; \backslash left(d^2\backslash log\_d\; n\backslash right)$ for deterministic designs, compared to $t\; =\; O(d\backslash log\_2\; n)$ for designs that allow arbitrarily small probabilities of error (as $d\; \backslash to\; \backslash infty$ and $n\; \backslash to\; \backslash infty$).}}

In this vein, Chan et al. (2011) introduced COMP, a probabilistic algorithm that requires no more than $t\; =\; ed(1+\backslash delta)\backslash ln(n)$ tests to find up to $d$ defectives in $n$ items with a probability of error no more than $n^\{-\backslash delta\}$. This is within a constant factor of the $t\; =\; O(d\backslash log\_2\; n)$ lower bound.

Chan et al. (2011) also provided a generalisation of COMP to a simple noisy model, and similarly produced an explicit performance bound, which was again only a constant (dependent on the likelihood of a failed test) above the corresponding lower bound. In general, the number of tests required in the Bernoulli noise case is a constant factor larger than in the noiseless case.

Aldridge, Baldassini and Johnson (2014) produced an extension of the COMP algorithm that added additional post-processing steps. They showed that the performance of this new algorithm, called DD, strictly exceeds that of COMP, and that DD is 'essentially optimal' in scenarios where $d^2\; \backslash geq\; n$, by comparing it to a hypothetical algorithm that defines a reasonable optimum. The performance of this hypothetical algorithm suggests that there is room for improvement when , as well as suggesting how much improvement this might be.

This section formally defines the notions and terms relating to group testing.

• The input vector, $\backslash mathbf\{x\}\; =\; (x\_1,\; x\_2,\; \backslash dots,\; x\_n)$, is defined to be a binary vector of length $n$ (that is, $\backslash mathbf\{x\}\; \backslash in\; \backslash \{0,1\backslash \}^n$), with the j-th item being called defective if and only if $x\_j=\; 1$. Further, any non-defective item is called a 'good' item.

$\backslash mathbf\{x\}$ is intended to describe the (unknown) set of defective items. The key property of $\backslash mathbf\{x\}$ is that it is an implicit input. That is to say, there is no direct knowledge of what the entries of $\backslash mathbf\{x\}$ are, other than that which can be inferred via some series of 'tests'. This leads on to the next definition.

• Let $\backslash mathbf\{x\}$ be an input vector. A set, $S\; \backslash subseteq\; \backslash \{\; 1,\; 2,\; \backslash dots,\; n\; \backslash \}$ is called a test. When testing is noiseless, the result of a test is positive when there exists $j\; \backslash in\; S$ such that $x\_j\; =\; 1$, and the result is negative otherwise.

Therefore, the goal of group testing is to come up with a method for choosing a 'short' series of tests that allow $\backslash mathbf\{x\}$ to be determined, either exactly or with a high degree of certainty.

• A group-testing algorithm is said to make an error if it incorrectly labels an item (that is, labels any defective item as non-defective or vice versa). This is not the same thing as the result of a group test being incorrect. An algorithm is called zero-error if the probability that it makes an error is zero.{{efn|One must be careful to distinguish between when a test reports a false result and when the group-testing procedure fails as a whole. It is both possible to make an error with no incorrect tests and to not make an error with some incorrect tests. Most modern combinatorial algorithms have some non-zero probability of error (even with no erroneous tests), since this significantly decreases the number of tests needed.}}
• $t(d,\; n)$ denotes the minimum number of tests required to always find $d$ defectives among $n$ items with zero probability of error by any group-testing algorithm. For the same quantity but with the restriction that the algorithm is non-adaptive, the notation $\backslash bar\{t\}(d,\; n)$ is used.

Since it is always possible to resort to individual testing by setting $S\_j\; =\; \backslash \{j\backslash \}$ for each $1\; \backslash leq\; j\; \backslash leq\; n$, it must be that that $\backslash bar\{t\}(d,\; n)\; \backslash leq\; n$. Also, since any non-adaptive testing procedure can be written as an adaptive algorithm by simply performing all the tests without regard to their outcome, $t(d,\; n)\; \backslash leq\; \backslash bar\{t\}(d,\; n)$. Finally, when $0\; \backslash neq\; d\; \backslash neq\; n$, there is at least one item whose defectiveness must be determined (by at least one test), and so $1\; \backslash leq\; t(d,\; n)$.

In summary (when assuming $0\; \backslash neq\; d\; \backslash neq\; n$), $1\; \backslash leq\; t(d,n)\; \backslash leq\; \backslash bar\{t\}(d,\; n)\; \backslash leq\; n$.{{efn|In fact it is possible to do much better. For example, Li's $s$-stage algorithm gives an explicit construction were $t\; \backslash leq\; \backslash frac\{e\}\{\backslash log\_2\; e\}\; d\; \backslash log\_2\{(n/d)\}$.}}

A lower bound on the number of tests needed can be described using the notion of sample space, denoted $\backslash mathcal\{S\}$, which is simply the set of possible placements of defectives. For any group testing problem with sample space $\backslash mathcal\{S\}$ and any group-testing algorithm, it can be shown that $t\; \backslash geq\; \backslash lceil\; \backslash log\_2$

File:Nonadaptive Group Testing.svg

Algorithms for non-adaptive group testing consist of two distinct phases. First, it is decided how many tests to perform and which items to include in each test. In the second phase, often called the decoding step, the results of each group test are analysed to determine which items are likely to be defective. The first phase is usually encoded in a matrix as follows.

• Suppose a non-adaptive group testing procedure for $n$ items consists of the tests $S\_1,\; S\_2,\; \backslash dots,\; S\_t$ for some $t\; \backslash in\; \backslash mathbb\{N\}\_\{\backslash geq\; 0\}$. The testing matrix for this scheme is the $t\; \backslash times\; n$ binary matrix, $M$, where $(M)\_\{ij\}\; =\; 1$ if and only if $j\; \backslash in\; S\_i$ (and is zero otherwise).

Thus each column of $M$ represents an item and each row represents a test, with a $1$ in the $(i,j)\backslash textrm\{-th\}$ entry indicating that the $i\backslash textrm\{-th\}$ test included the $j\backslash textrm\{-th\}$ item and a $0$ indicating otherwise.

As well as the vector $\backslash mathbf\{x\}$ (of length $n$) that describes the unknown defective set, it is common to introduce the result vector, which describes the results of each test.

• Let $t$ be the number of tests performed by a non-adaptive algorithm. The result vector, $\backslash mathbf\{y\}\; =\; (y\_1,\; y\_2,\; \backslash dots,\; y\_t)$, is a binary vector of length $t$ (that is, $\backslash mathbf\{y\}\; \backslash in\; \backslash \{0,1\backslash \}^t$) such that $y\_i=\; 1$ if and only if the result of the $i\backslash textrm\{-th\}$ test was positive (i.e. contained at least one defective).{{efn|Alternatively $\backslash mathbf\; \{y\}$ can be defined by the equation $\backslash mathbf\{y\}\; :=\; M\backslash mathbf\; \{x\}$, where multiplication is logical AND ($\backslash wedge$) and addition is logical OR ($\backslash vee$). Here, $\backslash mathbf\; \{y\}$ will have a $1$ in position $i$ if and only if $(M)\_\{i,j\}$ and $\backslash mathbf\; \{x\}\; \_\{j\}$ are both $1$ for any $j$. That is, if and only if at least one defective item was included in the $i\backslash textrm\{-th\}$ test.}}

With these definitions, the non-adaptive problem can be reframed as follows: first a testing matrix is chosen, $M$, after which the vector $\backslash mathbf\{y\}$ is returned. Then the problem is to analyse $\backslash mathbf\{y\}$ to find some estimate for $\backslash mathbf\{x\}$.

In the simplest noisy case, where there is a constant probability, $q$, that a group test will have an erroneous result, one considers a random binary vector, $\backslash mathbf\{v\}$, where each entry has a probability $q$ of being $1$, and is $0$ otherwise. The vector that is returned is then $\backslash hat\{\backslash mathbf\{y\}\}\; =\; \backslash mathbf\{y\}\; +\; \backslash mathbf\{v\}$, with the usual addition on $(\backslash mathbb\{Z\}/2\backslash mathbb\{Z\})^n$ (equivalently this is the element-wise XOR operation). A noisy algorithm must estimate $\backslash mathbf\{x\}$ using $\backslash hat\{\backslash mathbf\{y\}\}$ (that is, without direct knowledge of $\backslash mathbf\{y\}$).

The matrix representation makes it possible to prove some bounds on non-adaptive group testing. The approach mirrors that of many deterministic designs, where $d$-separable matrices are considered, as defined below.

• A binary matrix, $M$, is called $d$-separable if every Boolean sum (logical OR) of any $d$ of its columns is distinct. Additionally, the notation $\backslash bar\{d\}$-separable indicates that every sum of any of up to $d$ of $M$'s columns is distinct. (This is not the same as $M$ being $k$-separable for every $k\; \backslash leq\; d$.)

When $M$ is a testing matrix, the property of being $d$-separable ($\backslash bar\{d\}$-separable) is equivalent to being able to distinguish between (up to) $d$ defectives. However, it does not guarantee that this will be straightforward. A stronger property, called disjunctness does.

• A binary matrix, $M$ is called $d$-disjunct if the Boolean sum of any $d$ columns does not contain any other column. (In this context, a column A is said to contain a column B if for every index where B has a 1, A also has a 1.)

A useful property of $d$-disjunct testing matrices is that, with up to $d$ defectives, every non-defective item will appear in at least one test whose outcome is negative. This means there is a simple procedure for finding the defectives: just remove every item that appears in a negative test.

Using the properties of $d$-separable and $d$-disjunct matrices the following can be shown for the problem of identifying $d$ defectives among $n$ total items.

1. The number of tests needed for an asymptotically small average probability of error scales as $O(d\backslash log\_2\; n)$.
2. The number of tests needed for an asymptotically small maximum probability of error scales as $O(d^2\; \backslash log\_2\; n)$.
3. The number of tests needed for a zero probability of error scales as $O\; \backslash left(\backslash frac\{d^2\; \backslash log\_2\; n\}\{\backslash log\_2\; d\}\; \backslash right)$.

File:Generalised binary splitting.svg

The generalised binary-splitting algorithm is an essentially-optimal adaptive group-testing algorithm that finds $d$ or fewer defectives among $n$ items as follows:

{{cite journal

|last1=Hwang|first1=Frank K.

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

|journal=Journal of the American Statistical Association

|date=September 1972

|volume=67|issue=339

|pages=605–608

|doi=10.2307/2284447

|jstor=2284447}}

1. If $n\; \backslash leq\; 2d\; -\; 2$, test the $n$ items individually. Otherwise, set $l\; =\; n\; -\; d\; +\; 1$ and $\backslash alpha\; =\; \backslash lfloor\; \backslash log\_2\{l/d\}\; \backslash rfloor$.
2. Test a group of size $2^\backslash alpha$. If the outcome is negative, every item in the group is declared to be non-defective; set $n\; :=\; n\; -\; 2^\backslash alpha$ and go to step 1. Otherwise, use a binary search to identify one defective and an unspecified number, called $x$, of non-defective items; set $n\; :=\; n\; -\; 1\; -\; x$ and $d\; :=\; d\; -\; 1$. Go to step 1.

The generalised binary-splitting algorithm requires no more than $T$ tests where

T = \begin{cases}

n & n \leq 2d-2\\

(\alpha+2)d + p - 1 & n \geq 2d - 1

\end{cases}

.

For $n/d$ large, it can be shown that $T\; \backslash rightarrow\; d\; \backslash log\_2(n/d)$, which compares favorably to the $t\; =\; \backslash frac\{e\}\{\backslash log\_2\; e\}d\backslash log\_2\; \backslash left(\; \backslash frac\{n\}\{d\}\; \backslash right)$ tests required for Li's $s$-stage algorithm. In fact, the generalised binary-splitting algorithm is close to optimal in the following sense. When $d\; \backslash geq\; 2$ it can be shown that $T\; -\; B\_I(d,n)\; \backslash leq\; (d-1)$, where $B\_I(d,n)\; =\; \backslash left\backslash lceil\; \backslash log\_2\; \backslash sum\_\{i=0\}^d\; \{n\; \backslash choose\; i\}\; \backslash right\backslash rceil$ is the information lower bound.

Non-adaptive group-testing algorithms tend to assume that the number of defectives, or at least a good upper bound on them, is known.

{{cite conference

|arxiv=1107.4540

|author1=Chun Lam Chan

|title=Non-adaptive probabilistic group testing with noisy measurements: Near-optimal bounds with efficient algorithms

|author2=Pak Hou Che

|last3=Jaggi|first3=Sidharth

|last4=Saligrama|first4=Venkatesh

|date = 1 September 2011

|pages = 1832–9

|doi = 10.1109/Allerton.2011.6120391

|book-title = 49th Annual Allerton Conference on Communication, Control, and Computing|isbn=978-1-4577-1817-5

|s2cid=8408114

}}

This quantity is denoted $d$ in this section. If no bounds are known, there are non-adaptive algorithms with low query complexity that can help estimate $d$.{{cite journal

|last1=Sobel|first1=Milton

|last2=Elashoff|first2=R. M.

|title=Group testing with a new goal, estimation|journal=Biometrika

|date=1975

|volume=62

|issue=1

|pages=181–193

|doi=10.1093/biomet/62.1.181|hdl=11299/199154

|hdl-access=free

}}

File:COMP Algorithm.svg

Combinatorial Orthogonal Matching Pursuit, or COMP, is a simple non-adaptive group-testing algorithm that forms the basis for the more complicated algorithms that follow in this section.

First, each entry of the testing matrix is chosen i.i.d. to be $1$ with probability $1/d$ and $0$ otherwise.

The decoding step proceeds column-wise (i.e. by item). If every test in which an item appears is positive, then the item is declared defective; otherwise the item is assumed to be non-defective. Or equivalently, if an item appears in any test whose outcome is negative, the item is declared non-defective; otherwise the item is assumed to be defective. An important property of this algorithm is that it never creates false negatives, though a false positive occurs when all locations with ones in the j-th column of $M$ (corresponding to a non-defective item j) are "hidden" by the ones of other columns corresponding to defective items.

The COMP algorithm requires no more than $ed(1\; +\; \backslash delta)\; \backslash ln(n)$ tests to have an error probability less than or equal to $n^\{-\backslash delta\}$. This is within a constant factor of the lower bound for the average probability of error above.

In the noisy case, one relaxes the requirement in the original COMP algorithm that the set of locations of ones in any column of $M$ corresponding to a positive item be entirely contained in the set of locations of ones in the result vector. Instead, one allows for a certain number of “mismatches” – this number of mismatches depends on both the number of ones in each column, and also the noise parameter, $q$. This noisy COMP algorithm requires no more than $4.36(\backslash sqrt\{\backslash delta\}\; +\; \backslash sqrt\{1\; +\; \backslash delta\})^2\; (1\; -\; 2q)^\{-2\}d\; \backslash log\_2\{n\}$ tests to achieve an error probability at most $n^\{-\backslash delta\}$.

The definite defectives method (DD) is an extension of the COMP algorithm that attempts to remove any false positives. Performance guarantees for DD have been shown to strictly exceed those of COMP.{{cite journal

|last1=Aldridge|first1=Matthew

|last2=Baldassini|first2=Leonardo

|last3=Johnson|first3=Oliver

|title=Group Testing Algorithms: Bounds and Simulations

|journal=IEEE Transactions on Information Theory

|date=June 2014

|volume=60|issue=6

|pages=3671–3687

|doi=10.1109/TIT.2014.2314472|arxiv=1306.6438|s2cid=8885619

}}

The decoding step uses a useful property of the COMP algorithm: that every item that COMP declares non-defective is certainly non-defective (that is, there are no false negatives). It proceeds as follows.

1. First the COMP algorithm is run, and any non-defectives that it detects are removed. All remaining items are now "possibly defective".
2. Next the algorithm looks at all the positive tests. If an item appears as the only "possible defective" in a test, then it must be defective, so the algorithm declares it to be defective.
3. All other items are assumed to be non-defective. The justification for this last step comes from the assumption that the number of defectives is much smaller than the total number of items.

Note that steps 1 and 2 never make a mistake, so the algorithm can only make a mistake if it declares a defective item to be non-defective. Thus the DD algorithm can only create false negatives.

SCOMP (Sequential COMP) is an algorithm that makes use of the fact that DD makes no mistakes until the last step, where it is assumed that the remaining items are non-defective. Let the set of declared defectives be $K$. A positive test is called explained by $K$ if it contains at least one item in $K$. The key observation with SCOMP is that the set of defectives found by DD may not explain every positive test, and that every unexplained test must contain a hidden defective.

The algorithm proceeds as follows.

1. Carry out steps 1 and 2 of the DD algorithm to obtain $K$, an initial estimate for the set of defectives.
2. If $K$ explains every positive test, terminate the algorithm: $K$ is the final estimate for the set of defectives.
3. If there are any unexplained tests, find the "possible defective" that appears in the largest number of unexplained tests, and declare it to be defective (that is, add it to the set $K$). Go to step 2.

In simulations, SCOMP has been shown to perform close to optimally.

A deterministic algorithm that is guaranteed to exactly

identify up to $d$ positives is Polynomial Pools (PP).

.{{cite journal

|last1 = Brust|first1 = D.

|last2 = Brust|first2 = J. J.

|date = January 2023

|title = Effective matrix designs for COVID-19 group testing

|journal = BMC Bioinformatics

|volume = 24

|number = 26

|page = 26

|doi = 10.1186/s12859-023-05145-y

|pmid = 36694117

|pmc = 9872308

|doi-access = free

}} The algorithm is for the construction of the pooling matrix $M$, which can be straightforwardly used

to decode the observations in $y$. Similar to

COMP, a sample is decoded according to the relation:

$x\_i\; =\; 1\; ~~\; \backslash text\{\; if\; \}\; ~~\; M(:,i)~.*~y\; =\; M(:,i)$, where $.*$ represents element wise multiplication and $M(:,i)$ is the $i$th column of $M$. Since the decoding step is not difficult, PP is specialized for generating $M$.

File:Design k3 p3 n1 d3 l1S.svg

A group/pool $\backslash ell$ is

generated using a polynomial relation that specifies the indices of the samples contained in each pool. A set of input parameters determines the algorithm. For a prime number $p>1$ and an integer $n\; \backslash ge\; 1$ any prime power is defined by $q=p^n$. For a dimension parameter $c\; \backslash ge\; 2$ the total number of samples is $n\; =\; q^c$ and the number of samples per pool is $q^\{c-1\}$.

Further, the

Finite field of order $q$ is denoted by $\backslash mathbb\{F\}\_q$

(i.e., the integers $\backslash \{0,1,2,\backslash ldots,q-1\backslash \}$ defined by special arithmetic operations that ensure that addition and multiplication in $\backslash mathbb\{F\}\_q$ remains in $\backslash mathbb\{F\}\_q$).

The method arranges each sample in a grid and represents it by coordinates $x\; =\; (u,v)$. The coordinates are computed according to a polynomial relation using the integers

$1\; \backslash le\; l\; \backslash le\; c-1$, $0\; \backslash le\; u\_\{i\_l\}\; \backslash le\; q-1$

v~=~a^{c-1}~u_{i_{c-1}} + \cdots + a~u_{i_1} + b, \quad a, b, u_{i_l} \in \mathbb{F}_q.

The combination of looping through the $u\_\{i\_l\}$ values is represented by a set with $q^\{c-1\}$ elements of a sequence of $d-1$ integers, i.e.,

$u\_\{i\_1\}\; \backslash times\; \backslash cdots\; \backslash times\; u\_\{i\_\{c-1\}\}\; =\; \backslash \{(i\_1,\backslash ldots,i\_\{c-1\})\backslash \}$, where

$0\; \backslash le\; i\_l\; \backslash le\; q-1$. Without loss of generality, the combination is such that

$i\_\{d-1\}$ cycles every $q$ times, $i\_\{d-2\}$ cycles every $q^2$ times until

$i\_1$ cycles only once.

Formulas that compute the sample indices, and thus the corresponding pools, for fixed $a$ and $b$, are given by

\begin{align}

u_i &= \sum_{l=1}^{c-1}~q^{d-1-l}~i_l \\

v_{u_i} &= \sum_{l=1}^{c-1}~a^{l}~i_l + b\quad (\text{computed in } \mathbb{F}_q) \\

x_{q u_i + v_{u_i}} &= (u_i,v_{u_i})

\end{align}

The computations in $\backslash mathbb\{F\}\_q$ can be implemented with publicly available software libraries for finite fields, when $q$ is a prime power. When $q$ is a prime number then the computations in $\backslash mathbb\{F\}\_q$ simplify to modulus arithmetics, i.e., $v\_\{u\_i\}\; =\; (\backslash sum\_\{l=1\}^\{c-1\}a^\{l\}i\_l\; +\; b)\; ~\; \backslash text\{mod\}~q$. An example of how to generate one pool $\backslash ell$ when

$a\; =\; 1,\; b\; =\; 0,\; c\; =\; 2$ is displayed in the table below, while the corresponding selection of samples is shown in the figure above.

This method uses $q(c-1)(d+1)$ tests to exactly identify up to $d$ positives among $n\; =\; q^c$ samples.

Because of this PP is particularly effective for large sample sizes, since the number of tests grows only linearly with respect to $c$ while the samples grow exponentially with this parameter. However PP can also be effective for small sample sizes.

The generality of the theory of group testing lends it to many diverse applications, including clone screening, locating electrical shorts; high speed computer networks;{{Cite book

|last1 = Bar-Noy|first1 = A.

|last2 = Hwang|first2 = F. K.

|last3 = Kessler|first3 = I.

|last4 = Kutten|first4 = S.

|title = [Proceedings] IEEE INFOCOM '92: The Conference on Computer Communications

|chapter = A new competitive algorithm for group testing

|date = 1 May 1992

|pages = 786–793

|volume = 2

|doi = 10.1109/INFCOM.1992.263516

|isbn = 978-0-7803-0602-8

|s2cid = 16131063

}} medical examination, quantity searching, statistics; machine learning, DNA sequencing;{{cite journal

|last1 = Damaschke|first1 = Peter

|year = 2000

|title = Adaptive versus nonadaptive attribute-efficient learning

|journal = Machine Learning

|volume = 41|issue = 2

|pages = 197–215

|doi = 10.1023/A:1007616604496|doi-access = free

}} cryptography;{{cite journal

|last1 = Stinson|first1 = D. R.

|last2 = van Trung|first2 = Tran

|last3 = Wei|first3 = R

|date = May 2000

|title = Secure frameproof codes, key distribution patterns, group testing algorithms and related structures

|journal = Journal of Statistical Planning and Inference

|volume = 86|issue = 2

|pages = 595–617

|doi = 10.1016/S0378-3758(99)00131-7|citeseerx = 10.1.1.54.6212

}}{{cite journal

|last1 = Colbourn|first1 = C. J.

|last2 = Dinitz|first2 = J. H.

|last3 = Stinson|first3 = D. R.

|year = 1999

|title = Communications, Cryptography, and Networking

|journal = Surveys in Combinatorics

|volume = 3

|issue = 267

|pages = 37–41|doi = 10.1007/BF01609873

|s2cid = 10128581

|doi-access = free

}} and data forensics.{{Cite book

|last1 = Goodrich|first1 = Michael T.

|last2 = Atallah|first2 = Mikhail J.

|last3 = Tamassia|first3 = Roberto

|title = Applied Cryptography and Network Security

|chapter = Indexing Information for Data Forensics

|date = 2005

|volume = 3531

|pages = 206–221

|doi = 10.1007/11496137_15|series = Lecture Notes in Computer Science

|isbn = 978-3-540-26223-7

|citeseerx = 10.1.1.158.6036

}} This section provides a brief overview of a small selection of these applications.

File:Mutliaccess channel.svg

A multiaccess channel is a communication channel that connects many users at once. Every user can listen and transmit on the channel, but if more than one user transmits at the same time, the signals collide, and are reduced to unintelligible noise. Multiaccess channels are important for various real-world applications, notably wireless computer networks and phone networks.{{cite book |last=Chlebus |first=B.S. |year=2001 |chapter=Randomized communication in radio networks |editor-last=Pardalos |editor-first=P.M. |editor2-last=Rajasekaran |editor2-first=S. |editor3-last=Reif |editor3-first=J. |editor4-last=Rolim |editor4-first=J.D.P. |title=Handbook of Randomized Computing |pages=401–456 |publisher=Kluwer Academic |isbn=978-0-7923-6957-8 |chapter-url={{GBurl|ZGgnFGfHGroC|p=401}}}}

A prominent problem with multiaccess channels is how to assign transmission times to the users so that their messages do not collide. A simple method is to give each user their own time slot in which to transmit, requiring $n$ slots. (This is called time division multiplexing, or TDM.) However, this is very inefficient, since it will assign transmission slots to users that may not have a message, and it is usually assumed that only a few users will want to transmit at any given time – otherwise a multiaccess channel is not practical in the first place.

In the context of group testing, this problem is usually tackled by dividing time into 'epochs' in the following way. A user is called 'active' if they have a message at the start of an epoch. (If a message is generated during an epoch, the user only becomes active at the start of the next one.) An epoch ends when every active user has successfully transmitted their message. The problem is then to find all the active users in a given epoch, and schedule a time for them to transmit (if they have not already done so successfully). Here, a test on a set of users corresponds to those users attempting a transmission. The results of the test are the number of users that attempted to transmit, $0,\; 1,$ and $2^+$, corresponding respectively to no active users, exactly one active user (message successful) or more than one active user (message collision). Therefore, using an adaptive group testing algorithm with outcomes $\backslash \{\; 0,\; 1,\; 2^+\backslash \}$, it can be determined which users wish to transmit in the epoch. Then, any user that has not yet made a successful transmission can now be assigned a slot to transmit, without wastefully assigning times to inactive users.

Machine learning is a field of computer science that has many software applications such as DNA classification, fraud detection and targeted advertising. One of the main subfields of machine learning is the 'learning by examples' problem, where the task is to approximate some unknown function when given its value at a number of specific points. As outlined in this section, this function learning problem can be tackled with a group-testing approach.

In a simple version of the problem, there is some unknown function, $f:\; \backslash \{0,1\backslash \}^N\; \backslash to\; \backslash \{0,1\backslash \}$ where $f(\backslash textbf\{x\})\; =\; \backslash textbf\{a\}\; \backslash cdot\; \backslash textbf\{x\}$, and $\backslash textbf\{a\}\; \backslash in\; \backslash \{0,1\backslash \}^N$ (using logical arithmetic: addition is logical OR and multiplication is logical AND). Here $\backslash textbf\{a\}$ is '$d$ sparse', which means that at most $d\; \backslash ll\; N$ of its entries are $1$. The aim is to construct an approximation to $f$ using $t$ point evaluations, where $t$ is as small as possible. (Exactly recovering $f$ corresponds to zero-error algorithms, whereas $f$ is approximated by algorithms that have a non-zero probability of error.)

In this problem, recovering $f$ is equivalent to finding $\backslash textbf\{a\}$. Moreover, $f(\backslash textbf\{p\})\; =\; 1$ if and only if there is some index, $n$, where $\backslash textbf\{a\}\_n\; =\; \backslash textbf\{p\}\_n\; =\; 1$. Thus this problem is analogous to a group-testing problem with $d$ defectives and $n$ total items. The entries of $\backslash textbf\{a\}$ are the items, which are defective if they are $1$, $\backslash textbf\{p\}$ specifies a test, and a test is positive if and only if $f(\backslash textbf\{p\})\; =\; 1$.

In reality, one will often be interested in functions that are more complicated, such as $f:\; \backslash mathbb\{C\}^N\; \backslash to\; \backslash mathbb\{C\}$, again where $f(\backslash textbf\{x\})\; =\; \backslash textbf\{a\}\; \backslash cdot\; \backslash textbf\{x\}$. Compressed sensing, which is closely related to group testing, can be used to solve this problem.

In compressed sensing, the goal is to reconstruct a signal, $\backslash textbf\{v\}\; \backslash in\; \backslash mathbb\{C\}^N$, by taking a number of measurements. These measurements are modelled as taking the dot product of $\backslash textbf\{v\}$ with a chosen vector.{{efn|This kind of measurement comes up in many applications. For example, certain kinds of digital camera{{cite journal

|last1 = Takhar|first1 = D.

|last2 = Laska|first2 = J. N.

|last3 = Wakin|first3 = M. B.

|last4 = Duarte|first4 = M. F.

|last5 = Baron|first5 = D.

|last6 = Sarvotham|first6 = S.

|last7 = Kelly|first7 = K. F.

|last8 = Baraniuk|first8 = R. G.

|editor-first1 = Charles A.

|editor-first2 = Eric L.

|editor-first3 = Ilya

|editor-last1 = Bouman

|editor-last2 = Miller

|editor-last3 = Pollak

|date = February 2006

|title = A new compressive imaging camera architecture using optical-domain compression

|journal = Electronic Imaging

|volume = 6065

|pages = 606509–606509–10

|bibcode = 2006SPIE.6065...43T

|doi = 10.1117/12.659602

|series = Computational Imaging IV

|citeseerx = 10.1.1.114.7872

|s2cid = 7513433

}} or MRI machines,{{cite conference |last=Candès |first=E.J. |date=2014 |title=Mathematics of sparsity (and a few other things) |book-title=Proceedings of the International Congress of Mathematicians. Seoul, South Korea |url=}} where time constraints require that only a small number of measurements are taken.}} The aim is to use a small number of measurements, though this is typically not possible unless something is assumed about the signal. One such assumption (which is common{{cite conference |last1=Gilbert |first1=A.C. |last2=Iwen |first2=M.A. |last3=Strauss |first3=M.J. |date=October 2008 |title=Group testing and sparse signal recovery |book-title=42nd Asilomar Conference on Signals, Systems and Computers |pages=1059–63 |publisher=Institute of Electrical and Electronics Engineers |doi=10.1109/ACSSC.2008.5074574 |isbn=978-1-4244-2940-0}}{{cite journal

|last1 = Wright|first1 = S. J.

|last2 = Nowak|first2 = R. D.

|last3 = Figueiredo|first3 = M. A. T.

|date = July 2009

|title = Sparse Reconstruction by Separable Approximation

|journal = IEEE Transactions on Signal Processing

|volume = 57|issue = 7

|pages = 2479–2493

|doi = 10.1109/TSP.2009.2016892|bibcode = 2009ITSP...57.2479W|citeseerx = 10.1.1.142.749

|s2cid = 7399917

}}) is that only a small number of entries of $\backslash textbf\{v\}$ are significant, meaning that they have a large magnitude. Since the measurements are dot products of $\backslash textbf\{v\}$, the equation $M\backslash textbf\{v\}\; =\; \backslash textbf\{q\}$ holds, where $M$ is a $t\; \backslash times\; N$ matrix that describes the set of measurements that have been chosen and $\backslash mathbf\{q\}$ is the set of measurement results. This construction shows that compressed sensing is a kind of 'continuous' group testing.

The primary difficulty in compressed sensing is identifying which entries are significant. Once that is done, there are a variety of methods to estimate the actual values of the entries.{{Cite book

|last1 = Berinde|first1 = R.

|last2 = Gilbert|first2 = A. C.

|last3= Indyk|first3 = P.

|last4 = Karloff|first4 = H.

|last5 = Strauss|first5 = M. J.

|title = 2008 46th Annual Allerton Conference on Communication, Control, and Computing

|chapter = Combining geometry and combinatorics: A unified approach to sparse signal recovery

|date = September 2008

|pages = 798–805

|doi = 10.1109/ALLERTON.2008.4797639|arxiv = 0804.4666|isbn = 978-1-4244-2925-7

|s2cid = 8301134

}} This task of identification can be approached with a simple application of group testing. Here a group test produces a complex number: the sum of the entries that are tested. The outcome of a test is called positive if it produces a complex number with a large magnitude, which, given the assumption that the significant entries are sparse, indicates that at least one significant entry is contained in the test.

There are explicit deterministic constructions for this type of combinatorial search algorithm, requiring $d2^\{(\backslash log\_2\; \backslash log\_2\; N)^\{O(1)\}\}$ measurements.{{cite journal

|last1 = Indyk|first1 = Piotr

|date = 1 January 2008

|title = Explicit Constructions for Compressed Sensing of Sparse Signals

|journal = Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms

|pages = 30–33

}} However, as with group-testing, these are sub-optimal, and random constructions (such as COMP) can often recover $f$ sub-linearly in $N$.

During a pandemic such as the COVID-19 outbreak in 2020, virus detection assays are sometimes run using nonadaptive group testing designs.{{Cite web|last=Austin|first=David|title=AMS Feature Column — Pooling strategies for COVID-19 testing|url=http://www.ams.org/publicoutreach/feature-column/fc-2020-10|access-date=2020-10-03|website=American Mathematical Society|language=en}}{{Cite web|last=Prasanna|first=Dheeraj|title=Tapestry pooling|url=https://tapestry-pooling.herokuapp.com/|access-date=2020-10-03|website=tapestry-pooling.herokuapp.com|language=en}}{{Citation

| last1 = Chiani | first1 = M.

| last2 = Liva | first2 = G.

| last3 = Paolini | first3 = E.

| title = Identification-detection group testing protocols for COVID-19 at high prevalence

| journal = Scientific Reports

| volume = 12

| publisher = Springer Nature

| date = February 2022

| issue = 1

| page = 3250

| doi = 10.1038/s41598-022-07205-4

| pmid = 35228579

| pmc = 8885674

| arxiv = 2104.11305

| bibcode = 2022NatSR..12.3250C

| s2cid = 233387831

| doi-access = free

}}

One example was provided by the Origami Assays project which released open source group testing designs to run on a laboratory standard 96 well plate.{{cite web |url= https://www.smarterbetter.design/origamiassays/default/index |title= Origami Assays |publisher= Origami Assays |access-date=April 7, 2020|date =April 2, 2020 }}

File:Origami Assays paper template used for multiplexing COVID19 assays.jpg

In a laboratory setting, one challenge of group testing is the construction of the mixtures can be time-consuming and difficult to do accurately by hand. Origami assays provided a workaround for this construction problem by providing paper templates to guide the technician on how to allocate patient samples across the test wells.{{cite web |url=https://www.smarterbetter.design/origamiassays/default/instructions |title= Origami Assays |publisher= Origami Assays |access-date=April 7, 2020|date =April 2, 2020 }}

Using the largest group testing designs (XL3) it was possible to test 1120 patient samples in 94 assay wells. If the true positive rate was low enough, then no additional testing was required.

{{See also|List of countries implementing pool testing strategy against COVID-19}}

Data forensics is a field dedicated to finding methods for compiling digital evidence of a crime. Such crimes typically involve an adversary modifying the data, documents or databases of a victim, with examples including the altering of tax records, a virus hiding its presence, or an identity thief modifying personal data.

A common tool in data forensics is the one-way cryptographic hash. This is a function that takes the data, and through a difficult-to-reverse procedure, produces a unique number called a hash.{{efn|More formally hashes have a property called collision resistance, which is that the likelihood of the same hash resulting from different inputs is very low for data of an appropriate size. In practice, the chance that two different inputs might produce the same hash is often ignored.}} Hashes, which are often much shorter than the data, allow us to check if the data has been changed without having to wastefully store complete copies of the information: the hash for the current data can be compared with a past hash to determine if any changes have occurred. An unfortunate property of this method is that, although it is easy to tell if the data has been modified, there is no way of determining how: that is, it is impossible to recover which part of the data has changed.

One way to get around this limitation is to store more hashes – now of subsets of the data structure – to narrow down where the attack has occurred. However, to find the exact location of the attack with a naive approach, a hash would need to be stored for every datum in the structure, which would defeat the point of the hashes in the first place. (One may as well store a regular copy of the data.) Group testing can be used to dramatically reduce the number of hashes that need to be stored. A test becomes a comparison between the stored and current hashes, which is positive when there is a mismatch. This indicates that at least one edited datum (which is taken as defectiveness in this model) is contained in the group that generated the current hash.

In fact, the amount of hashes needed is so low that they, along with the testing matrix they refer to, can even be stored within the organisational structure of the data itself. This means that as far as memory is concerned the test can be performed 'for free'. (This is true with the exception of a master-key/password that is used to secretly determine the hashing function.)

{{notelist}}

{{reflist|30em}}

• {{cite book

|last1=Ding-Zhu|first1= Du

|last2=Hwang|first2=Frank K.

|title=Combinatorial group testing and its applications

|date=1993

|publisher=World Scientific

|location=Singapore

|isbn=978-9810212933}}

• Atri Rudra's course on Error Correcting Codes: Combinatorics, Algorithms, and Applications (Spring 2007), Lectures [https://cse.buffalo.edu/faculty/atri/courses/coding-theory/lectures/lect7.pdf 7].
• Atri Rudra's course on Error Correcting Codes: Combinatorics, Algorithms, and Applications (Spring 2010), Lectures [https://cse.buffalo.edu/faculty/atri/courses/coding-theory/spr10/lectures/lect10.pdf 10], [https://cse.buffalo.edu/faculty/atri/courses/coding-theory/spr10/lectures/lect11.pdf 11], [https://cse.buffalo.edu/faculty/atri/courses/coding-theory/spr10/lectures/lect28.pdf 28], [https://cse.buffalo.edu/faculty/atri/courses/coding-theory/spr10/lectures/lect29.pdf 29]
• {{cite book |last1=Du |first1=D. |last2=Hwang |first2=F. |title=Pooling Designs and Nonadaptive Group Testing |publisher=World Scientific |location= |date=2006 |isbn=9789814477864 |url={{GBurl|mr_ICgAAQBAJ|pg=PR7}}}}
• {{cite journal |last1=Aldridge |first1=M. |last2=Johnson |first2=O. |last3=Scarlett |first3=J. |title=Group Testing: An Information Theory Perspective |journal=Foundations and Trends in Communications and Information Theory |volume=15 |issue=3–4 |pages=196–392 |date=2019 |doi=10.1561/0100000099|s2cid=62841593 |url=http://eprints.whiterose.ac.uk/151615/1/Group_Testing__An_Information_Theory_Perspective__2_%20%281%29.pdf }}
• {{cite journal |last1=Porat |first1=E. |last2=Rothschild |first2=A. |title=Explicit nonadaptive combinatorial group testing schemes |journal=IEEE Transactions on Information Theory |volume=57 |issue=12 |pages=7982–89 |date=2011 |doi=10.1109/TIT.2011.2163296 |arxiv=0712.3876 |s2cid=8815474 }}
• {{citation

|last1=Kagan|first1=Eugene

|last2=Ben-gal|first2=Irad

|title=A group testing algorithm with online informational learning

|journal=IIE Transactions

|year=2014

|volume=46

|issue=2

|pages=164–184

|issn=0740-817X

|doi=10.1080/0740817X.2013.803639

|s2cid=18588494

|ref=no}}

• Balance puzzle

Category:Combinatorics

Category:Design of experiments