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.

-knowledge of probability theory is required

-programming skills are desirable