グループテスト
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 + \delta) \ln(n) tests to have an error probability less than or equal to n^{-\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(\sqrt{\delta} + \sqrt{1 + \delta})^2 (1 - 2q)^{-2}d \log_2{n} tests to achieve an error probability at most n^{-\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.
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.
First the COMP algorithm is run, and any non-defectives that it detects are removed. All remaining items are now "possibly defective".
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.
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.
Carry out steps 1 and 2 of the DD algorithm to obtain K, an initial estimate for the set of defectives.
If K explains every positive test, terminate the algorithm: K is the final estimate for the set of defectives.
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.
The generality of the theory of group testing lends it to many diverse applications, including clone screening, locating electrical shorts; high speed computer networks; medical examination, quantity searching, statistics; machine learning, DNA sequencing; cryptography; and data forensics. This section provides a brief overview of a small selection of these applications.
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.
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 \{ 0, 1, 2^+\}, 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: \{0,1\}^N \to \{0,1\} where f(\textbf{x}) = \textbf{a} \cdot \textbf{x}, and \textbf{a} \in \{0,1\}^N (using logical arithmetic: addition is logical OR and multiplication is logical AND). Here \textbf{a} is 'd sparse', which means that at most d \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 \textbf{a}. Moreover, f(\textbf{p}) = 1 if and only if there is some index, n, where \textbf{a}_n = \textbf{p}_n = 1. Thus this problem is analogous to a group-testing problem with d defectives and n total items. The entries of \textbf{a} are the items, which are defective if they are 1, \textbf{p} specifies a test, and a test is positive if and only if f(\textbf{p}) = 1.
In reality, one will often be interested in functions that are more complicated, such as f: \mathbb{C}^N \to \mathbb{C}, again where f(\textbf{x}) = \textbf{a} \cdot \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, \textbf{v} \in \mathbb{C}^N, by taking a number of measurements. These measurements are modelled as taking the dot product of \textbf{v} with a chosen vector.This kind of measurement comes up in many applications. For example, certain kinds of digital camera or MRI machines, 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) is that only a small number of entries of \textbf{v} are significant, meaning that they have a large magnitude. Since the measurements are dot products of \textbf{v}, the equation M\textbf{v} = \textbf{q} holds, where M is a t \times N matrix that describes the set of measurements that have been chosen and \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. 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^{(\log_2 \log_2 N)^{O(1)} measurements. 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. 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.
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.
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.
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.