Capacity conjecture for nonadaptive group testing
Capacity conjecture for nonadaptive group testing
Consider either combinatorial nonadaptive group testing, where uniformly randomly chosen items among are defective, or probabilistic nonadaptive group testing, where each of the items is independently defective with probability . Define
Consider an asymptotic regime in which , , and for some . The capacity conjecture. If for some , there exists a test design and decoding algorithm whose error probability tends to as . If , then for any test design and decoding algorithm the error probability is bounded away from as . In particular, when for some , the capacity of nonadaptive probabilistic and combinatorial group testing is
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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.