Difference between revisions of "Open Problems:33"

From Open Problems in Sublinear Algorithms
Jump to: navigation, search
(Created page with "{{DISPLAYTITLE:Problem 33: Group Testing}} {{Infobox |label1 = Proposed by |data1 = Ely Porat |label2 = Source |data2 = Kanpur 2009 |label3 = Short l...")
 
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
|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.  
 
Given a set $S\subset [n]$ of size at most $k$, we want to identify $S$ by the following 2-stage process.  

Revision as of 05:27, 16 November 2012

Suggested by Ely Porat
Source Kanpur 2009
Short link https://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.

  1. 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$.
  2. 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 [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)$?