Picture of Ilya Vorobyev

Ilya Vorobyev

Technical University of Munich

Chair of Communications Engineering (Prof. Kramer)

Postal address

Theresienstr. 90
80333 München


Available Theses

Group testing with approximate recovery in linear regime

group testing


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


Theses in Progress