グループテスト
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.
t ( d , n ) {\displaystyle t(d,n)} denotes the minimum number of tests required to always find d {\displaystyle d} defectives among n {\displaystyle 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 t ̄ ( d , n ) {\displaystyle {\bar {t}}(d,n)} is used.
Considerable improvements to this were made in 2013 by Allemann, getting the required number of tests to less than 0.187 d + 0.5 log 2  ( d ) + 5.5 {\displaystyle 0.187d+0.5\log _{2}(d)+5.5} above the information lower bound when n / d ≥ 38 {\displaystyle n/d\geq 38} and d ≥ 10 {\displaystyle d\geq 10} . 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.
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, v ∈ C N {\displaystyle {\textbf {v}}\in \mathbb {C} ^{N}} , by taking a number of measurements. These measurements are modelled as taking the dot product of v {\displaystyle {\textbf {v}}} with a chosen vector. 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 v {\displaystyle {\textbf {v}}} are significant, meaning that they have a large magnitude.