# Bounds for the Number of Tests in Non-Adaptive Randomized Algorithms for Group Testing

arXiv: https://arxiv.org/abs/1911.01694 · HTML: https://mlsanity.com/paper/1911.01694/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 Nov 2019.

## Built on by (most cited first, 1 of 1)

- [On Detecting Some Defective Items in Group Testing](https://mlsanity.com/paper/2307.04822/) (2023)

## Abstract (arXiv)

We study the group testing problem with non-adaptive randomized algorithms. Several models have been discussed in the literature to determine how to randomly choose the tests. For a model cal M, let mcal M(n,d) be the minimum number of tests required to detect at most d defectives within n items, with success probability at least 1-δ, for some constant δ. In this paper, we study the measures ccal M(d)=limn→ ∞ fracmcal M(n,d)ln n mbox and  ccal M=limd→ ∞ fracccal M(d)d. In the literature, the analyses of such models only give upper bounds for ccal M(d) and ccal M, and for some of them, the bounds are not tight. We give new analyses that yield tight bounds for ccal M(d) and ccal M for all the known models~cal M.