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 ORCID: 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

[thumbnail of Group%20testing%20lies.pdf]
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: 11 May 2023 11:51

Citation Data

Cited 1 time in Scopus. View in Scopus. Powered By Scopus® Data

Actions (repository staff only)

Edit Item Edit Item


Downloads per month over past year

View more statistics