Problem 95: Non-Adaptive Group Testing

From Open Problems in Sublinear Algorithms
Revision as of 20:40, 26 August 2019 by Ccanonne (talk | contribs)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search
Suggested by Oliver Gebhard
Source WOLA 2019
Short link

In (non-adaptive) quantitative group testing, one has a population of $n$ individuals, among which $k=n^c$ (for some constant $c\in(0,1)$) are sick. The goal is to identify the $k$ sick individuals by performing $m$ non-adaptive tests. In each test, one specifies a subset $S\subseteq [n]$ and learns whether $S$ contains one or more sick individuals.

By a counting argument, one gets a lower bound of $m = \Omega\bigl( \frac{k}{\log k}\log \frac{n}{k} \bigr)$ tests; however, the best known upper bound is $m = O( k\log \frac{n}{k} )$.

Question: Can one get rid of the $\log k$ factor in the lower bound; or, conversely, improve the upper bound to match it?