## Group testing with approximate recovery in linear regime

**Keywords:**

group testing

#### Description

In the group testing problem, the goal is to identify a small subset of defective items of size **k** within a larger set of items of size **n**, based on a number **T** of tests.

In the paper [1] the authors analyze doubly-regular random design for non-adaptive group testing. In particular, they consider setting with approximate recovery in linear regime, when the number of defectives is linear and equals **k=pn**. Approximate recovery means that it is allowed to make a mistake, as long as the probability that an element is classified incorrectly is lower than some fixed **ε****>0**. There are two types of error: false-positive and false-negative. Define a false-positive rate (FPR) as the probability that a non-defective item(picked uniformly at random) is declared defective. False-negative rate (FNR) is defined as the probability that a defective item (picked uniformly at random) is declared non-defective.

The authors use DD (definitely defective) algorithm, which always has FPR=0. They evaluate a rate of a random code, generate with doubly-regular design. However, due to the properties of this designs, the graph of the rate depending on parameter **p** looks discontinuous. It suggests that their design is suboptimal and can be improved. Some of the possible approaches are to use different designs, such as Bernoulli design or design with a constant column weight. It is also possible to modify a doubly-regular design by considering different parameters **s** for submatrices **X_1, ..., X_r** (see paper [1] for details).

In this project it is suggested to improve the results of the paper [1] by considering one of the aforementioned designs.

[1] Tan, N., Tan, W., & Scarlett, J. (2022). Performance Bounds for Group Testing With Doubly-Regular Designs. *arXiv preprint arXiv:2201.03745*.

#### Prerequisites

-knowledge of probability theory is required

-programming skills are desirable