Difference between revisions of "Open Problems:95"
(Created page with "{{Header |title=Non-Adaptive Group Testing |source=wola19 |who=Oliver Gebhard }} In (non-adaptive) quantitative group testing, one has a population of $n$ individuals, among w...") |
m |
||
| Line 4: | Line 4: | ||
|who=Oliver Gebhard | |who=Oliver Gebhard | ||
}} | }} | ||
| − | 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 | + | 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 identity 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\ | + | 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? | '''Question:''' Can one get rid of the $\log k$ factor in the lower bound; or, conversely, improve the upper bound to match it? | ||
Revision as of 01:42, 25 August 2019
| Suggested by | Oliver Gebhard |
|---|---|
| Source | WOLA 2019 |
| Short link | https://sublinear.info/95 |
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 identity 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?
