Open Problems:95 - Revision history

Ccanonne at 20:40, 26 August 2019

2019-08-26T20:40:07Z

Krzysztof Onak: Updating the header

2019-08-26T18:11:33Z

Updating the header

Krzysztof Onak: Krzysztof Onak moved page Waiting:Non-Adaptive Group Testing to Open Problems:95 without leaving a redirect

2019-08-26T18:10:23Z

Krzysztof Onak moved page Waiting:Non-Adaptive Group Testing to Open Problems:95 without leaving a redirect

Krzysztof Onak at 01:42, 25 August 2019

2019-08-25T01:42:09Z

Ccanonne: 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..."

2019-08-07T20:26:34Z

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..."

New page

{{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 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?

@@ Line 3: / Line 3: @@
 |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 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.
+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?

@@ Line 1: / Line 1: @@
 {{Header
 |source=wola19
 |who=Oliver Gebhard

← Older revision	Revision as of 18:10, 26 August 2019
(No difference)