Capacity conjecture for nonadaptive group testing

Consider either combinatorial nonadaptive group testing, where kk uniformly randomly chosen items among nn are defective, or probabilistic nonadaptive group testing, where each of the nn items is independently defective with probability p=k/np=k/n. Define

T=T(n)=max{klog2nk,  1(ln2)2klnk}.T^*=T^*(n)=\max\left\{k\log_2\frac{n}{k},\;\frac{1}{(\ln 2)^2}k\ln k\right\}.

Consider an asymptotic regime in which k=o(n)k=o(n), kk\to\infty, and T<(1δ)nT^*<(1-\delta)n for some δ>0\delta>0. The capacity conjecture. If T>(1+ϵ)TT>(1+\epsilon)T^* for some ϵ>0\epsilon>0, there exists a test design and decoding algorithm whose error probability tends to 00 as nn\to\infty. If T<(1ϵ)TT<(1-\epsilon)T^*, then for any test design and decoding algorithm the error probability is bounded away from 00 as nn\to\infty. In particular, when k=Θ(nθ)k=\Theta(n^\theta) for some θ(0,1)\theta\in(0,1), the capacity of nonadaptive probabilistic and combinatorial group testing is

C=min{1,  ln21θθ}.C=\min\left\{1,\;\ln 2\,\frac{1-\theta}{\theta}\right\}.

The first minimand is the trivial counting bound. Achievability is known in some parameter ranges for combinatorial testing and has been supported nonrigorously for probabilistic testing, but a matching design- and algorithm-independent converse for the second minimand remains missing in the source.

Sources & referencesView supporting material

Primary source

Matthew Aldridge, “Conservative two-stage group testing in the linear regime”, arXiv:2005.06617 (2022).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.