CPL - Chalmers Publication Library
| Utbildning | Forskning | Styrkeområden | Om Chalmers | In English In English Ej inloggad.

Threshold group testing

Peter Damaschke (Institutionen för data- och informationsteknik, Datavetenskap, Algoritmer (Chalmers) ; Institutionen för data- och informationsteknik, Datavetenskap, Bioinformatik (Chalmers))
General Theory of Information Transfer and Combinatorics, Lecture Notes in Computer Science Vol. 4123 (2006), p. 707-718.
[Konferensbidrag, refereegranskat]

We introduce a natural generalization of the well-studied group testing problem: A test gives a positive (negative) answer if the pool contains at least u (at most l) positive elements, and an arbitrary answer if the number of positive elements is between these fixed thresholds l and u. We show that the p positive elements can be determined up to a constant number of misclassifications, bounded by the gap between the thresholds. This is in a sense the best possible result. Then we study the number of tests needed to achieve this goal if n elements are given. If the gap is zero, the complexity is, similarly to classical group testing, O(p log n) for any fixed u. For the general case we propose a two-phase strategy consisting of a Distill and a Compress phase. We obtain some tradeoffs between classification accuracy and the number of tests.

Nyckelord: combinatorial search, group testing, guessing secrets

Denna post skapades 2006-12-19. Senast ändrad 2015-02-11.
CPL Pubid: 24449