Open Problems:33 - Revision history

Krzysztof Onak: updated header

2013-03-07T01:51:51Z

updated header

Krzysztof Onak at 05:27, 16 November 2012

2012-11-16T05:27:15Z

Krzysztof Onak: Created page with "{{DISPLAYTITLE:Problem 33: Group Testing}} {{Infobox |label1 = Proposed by |data1 = Ely Porat |label2 = Source |data2 = Kanpur 2009 |label3 = Short l..."

2012-11-13T01:35:53Z

Created page with "{{DISPLAYTITLE:Problem 33: Group Testing}} {{Infobox |label1 = Proposed by |data1 = Ely Porat |label2 = Source |data2 = Kanpur 2009 |label3 = Short l..."

New page

{{DISPLAYTITLE:Problem 33: Group Testing}}
{{Infobox
|label1 = Proposed by
|data1 = Ely Porat
|label2 = Source
|data2 = [[Workshops:Kanpur_2009|Kanpur 2009]]
|label3 = Short link
|data3 = http://sublinear.info/33
}}
Given a set $S\subset [n]$ of size at most $k$, we want to identify $S$ by the following 2-stage process.
# We choose a set of subsets $T_1, \ldots, T_m \subset [n]$. For each $T_i$ we learn whether or not $T_i\cap S=\emptyset$.
# Based on the outcomes of the first $m$ tests, we may choose $j_1, \ldots, j_{O(k)}\in [n]$. For each $j_i$ we learn whether or not $j_i\in S$.

The goal is to minimize $m$, the number of tests performed in the first stage. Without any further restrictions it has been shown that $m=O(k\log n/k)$ suffices {{cite|BonisGV-05}}. However, for various pattern matching applications, we have the constraint that each $T_i$ needs to be an arithmetic progression, e.g., $T_i=\{2,8,14,20, \ldots \}$. In this case, $m=O(k\log^2 n)$ suffices. Is it possible to decrease this to $m=O(k\log n)$?

@@ Line 1: / Line 1: @@
 {{Header
 |source=kanpur09
 |who=Ely Porat

@@ Line 1: / Line 1: @@
-{{DISPLAYTITLE:Problem 33: Group Testing}}
+{{Header
-{{Infobox
+|title=Group Testing
-|label1 = Proposed by
+|source=kanpur09
-|data1 = Ely Porat
+|who=Ely Porat
 }}
 Given a set $S\subset [n]$ of size at most $k$, we want to identify $S$ by the following 2-stage process.