# Non-Adaptive Group Testing

Suggested by | Oliver Gebhard |
---|---|

Source | wola19 |

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, by performing $m$ non-adaptive tests, to identity the $k$ sick individuals (where a test is a subset $S\subseteq [n]$, whose output is $1$ if $S$ contains at least one sick individual).

By a counting argument, one gets a lower bound of $m = \Omega\big( \frac{k}{\log k}\log \frac{n}{k} \big)$ 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?