ProbXiv
Explorersign in
Problem archiveProblem record

Statement

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⁡{klog⁡2nk,  1(ln⁡2)2kln⁡k}.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), k→∞k\to\infty, and T∗<(1−δ)nT^*<(1-\delta)n for some δ>0\delta>0. The capacity conjecture. If T>(1+ϵ)T∗T>(1+\epsilon)T^* for some ϵ>0\epsilon>0, there exists a test design and decoding algorithm whose error probability tends to 00 as n→∞n\to\infty. If T<(1−ϵ)T∗T<(1-\epsilon)T^*, then for any test design and decoding algorithm the error probability is bounded away from 00 as n→∞n\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,  ln⁡2 1−θθ}.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.

Record

Comments

Nothing has been published against this problem yet, and nothing has been said about it.

Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.

Sign in

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.