Capacity conjecture for nonadaptive group testing
Statement
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.
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 inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.