Cardiff University | Prifysgol Caerdydd ORCA
Online Research @ Cardiff 
WelshClear Cookie - decide language by browser settings

Nonadaptive group testing with lies: Probabilistic existence theorems

Zhigljavsky, Anatoly Alexandrovich 2010. Nonadaptive group testing with lies: Probabilistic existence theorems. Journal of Statistical Planning and Inference 140 (10) , pp. 2825-2893. 10.1016/j.jspi.2010.03.012

Download (186kB) | Preview


We consider a wide range of combinatorial group testing problems with lies including binary, additive and multiaccess channel group testing problems. We derive upper bounds for the number of tests in the optimal nonadaptive algorithms. The derivation is probabilistic and is therefore non-constructive; it does not provide the way of constructing optimal algorithms. In the asymptotic setting, we show that the leading term for the number of tests does not depend on the number of lies and it is thus the same as for the zero-lie case. However, the other terms in the asymptotic upper bounds depend on the number of lies and substantially influence the upper bounds in the non-asymptotic situation.

Item Type: Article
Date Type: Publication
Status: Published
Schools: Mathematics
Subjects: Q Science > QA Mathematics
Uncontrolled Keywords: Probabilistic method; Existence theorems; Group testing; Significant factors; Multiaccess channel; Searching with lies
Publisher: Elsevier
ISSN: 0378-3758
Last Modified: 04 Jun 2017 03:00

Actions (repository staff only)

Edit Item Edit Item


Downloads per month over past year

View more statistics