Picture of Ilya Vorobyev

Ilya Vorobyev

Technical University of Munich

Chair of Communications Engineering (Prof. Kramer)

Postal address

Postal:
Theresienstr. 90
80333 München

Theses

Available Theses

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

Supervisor:

Theses in Progress

Publications

2023

  • Akhmejanova, Margarita; Olmezov, Konstantin; Volostnov, Aleksei; Vorobyev, Ilya; Vorob’ev, Konstantin; Yarovikov, Yury: Wiener index and graphs, almost half of whose vertices satisfy Šoltés property. Discrete Applied Mathematics 325, 2023, 37-42 more… Full text ( DOI )

2022

  • Gu, Yujie; Vorobyev, Ilya; Miao, Ying: Secure codes with list decoding. 2022 IEEE International Symposium on Information Theory (ISIT), IEEE, 2022 more… Full text ( DOI )
  • Vorobyev, Ilya: Complete traceability multimedia fingerprinting codes resistant to averaging attack and adversarial noise with optimal rate. Designs, Codes and Cryptography, 2022 more… Full text ( DOI )
  • Vorob’ev, I. V.; Lebedev, V. S.: Improved Upper Bounds for the Rate of Separating and Completely Separating Codes. Problems of Information Transmission 58 (3), 2022, 242-253 more… Full text ( DOI )

2021

  • Bitar, Rawad; Hanna, Serge Kas; Polyanskii, Nikita; Vorobyev, Ilya: Optimal Codes Correcting Localized Deletions. 2021 IEEE International Symposium on Information Theory (ISIT), IEEE, 2021 more… Full text ( DOI )
  • Holzbaur, Lukas; Polyanskaya, Rina; Polyanskii, Nikita; Vorobyev, Ilya; Yaakobi, Eitan: Lifted Reed-Solomon Codes and Lifted Multiplicity Codes. IEEE Transactions on Information Theory 67 (12), 2021, 8051--8069 more… Full text ( DOI )
  • Holzbaur, Lukas; Polyanskaya, Rina; Polyanskii, Nikita; Vorobyev, Ilya; Yaakobi, Eitan: On Lifted Multiplicity Codes. 2020 IEEE Information Theory Workshop (ITW), IEEE, 2021 more… Full text ( DOI )
  • Liu, Hedongliang; Polianskii, Nikita; Vorobyev, Ilya; Wachter-Zeh, Antonia: Almost affinely disjoint subspaces. Finite Fields and Their Applications 75, 2021, 101879 more… Full text ( DOI )
  • Maringer, G.; Polyanskii, N. A.; Vorobyev, I. V.; Welter, L.: Feedback Insertion-Deletion Codes. Problems of Information Transmission 57 (3), 2021, 212-240 more… Full text ( DOI )
  • Maringer, Georg; Polyanskii, Nikita; Vorobyev, Ilya; Welter, Lorenz: Feedback Insertion-Deletion Codes. 2020 IEEE Information Theory Workshop (ITW), IEEE, 2021 more… Full text ( DOI )
  • Vorobyev, Ilya: Fast Decoding of Union-Free Codes. 2021 XVII International Symposium "Problems of Redundancy in Information and Control Systems" (REDUNDANCY), IEEE, 2021 more… Full text ( DOI )

2020

  • Holzbaur, Lukas; Polyanskaya, Rina; Polyanskii, Nikita; Vorobyev, Ilya: Lifted Reed-Solomon Codes with Application to Batch Codes. 2020 IEEE International Symposium on Information Theory (ISIT), IEEE, 2020 more… Full text ( DOI )
  • Polyanskaya, Rina; Polyanskii, Nikita; Vorobyev, Ilya: Binary Batch Codes With Improved Redundancy. IEEE Transactions on Information Theory 66 (12), 2020, 7360--7370 more… Full text ( DOI )
  • Polyanskii, Nikita; Vorobyev, Ilya: Duplication with transposition distance to the root for q-ary strings. 2020 IEEE International Symposium on Information Theory (ISIT), IEEE, 2020 more… Full text ( DOI )
  • Vorobyev, Ilya: Optimal Multistage Group Testing Algorithm for 3 Defectives. 2020 IEEE International Symposium on Information Theory (ISIT), IEEE, 2020 more… Full text ( DOI )

2019

  • D′yachkov, Arkadii; Polyanskii, Nikita; Shchukin, Vladislav; Vorobyev, Ilya: Separable Codes for the Symmetric Multiple-Access Channel. IEEE Transactions on Information Theory 65 (6), 2019, 3738--3750 more… Full text ( DOI )
  • D′yachkov, Arkadii; Polyanskii, Nikita; Shchukin, Vladislav; Vorobyev, Ilya: Hypothesis Test for Bounds on the Size of Random Defective Set. IEEE Transactions on Signal Processing 67 (22), 2019, 5775--5784 more… Full text ( DOI )
  • Egorova, Elena; Vorobyev, Ilya: New lower bound on the rate of traceability set systems. 2019 XVI International Symposium" Problems of Redundancy in Information and Control Systems"(REDUNDANCY), 2019 more…
  • Jiang, Zilin; Polyanskii, Nikita; Vorobyev, Ilya: On Capacities of the Two-User Union Channel With Complete Feedback. IEEE Transactions on Information Theory 65 (5), 2019, 2774--2781 more… Full text ( DOI )
  • Polyanskii, Nikita; Vorobyev, Ilya: Constructions of batch codes via finite geometry. 2019 IEEE International Symposium on Information Theory (ISIT), 2019 more…
  • Polyanskii, Nikita; Vorobyev, Ilya: Trivariate lifted codes with disjoint repair groups. 2019 XVI International Symposium" Problems of Redundancy in Information and Control Systems"(REDUNDANCY), 2019 more…
  • Vorobyev, Ilya: A new algorithm for two-stage group testing. 2019 IEEE International Symposium on Information Theory (ISIT), 2019 more…
  • Vorobyev, Ilya; Usatyuk, Vasiliy;: Construction of High Performance Block and Convolutional Multi-Edge Type QC-LDPC codes. 2019 42nd International Conference on Telecommunications and Signal Processing (TSP), 2019 more… Full text ( DOI )

2018

  • D′yachkov, Arkadii; Polyanskii, Nikita; Shchukin, Vladislav; Vorobyev, Ilya: Separable Codes for the Symmetric Multiple-Access Channel. 2018 IEEE International Symposium on Information Theory (ISIT), 2018 more… Full text ( DOI )
  • Usatyuk, Vasiliy; Vorobyev, Ilya: Simulated Annealing Method for Construction of High-Girth QC-LDPC Codes. 2018 41st International Conference on Telecommunications and Signal Processing (TSP), 2018 more…
  • Vorobyev, Ilya; Polyanskii, Nikita; Svistunov, German; Egorov, Sergey; Usatyuk, Vasiliy: Generalization of Floor Lifting for QC-LDPC Codes: Theoretical Properties and Applications. 2018 IEEE East-West Design & Test Symposium (EWDTS), 2018 more…

2017

  • D'yachkov, A.; Vorobyev, I.; Polyanskii, N.; Shchukin, V.: Almost cover-free codes and designs. Designs, Codes, and Cryptography 82 (1-2), 2017, 231-247 more…
  • D'yachkov, A.G.; Vorobyev, I.V.; Polyanskii, N.A.; Shchukin, V.Y.: Cover-free codes and separating system codes. Designs, Codes, and Cryptography 82 (1-2), 2017, 197-209 more…
  • D'yachkov, A.G.; Vorobyev, I.V.; Polyanskii, N.A.; Shchukin, V.Y.: Symmetric disjunctive list-decoding codes. Designs, Codes, and Cryptography 82 (1-2), 2017, 211-229 more…
  • D′yachkov, A.; Vorobyev, I.; Polyanskii, N.; Shchukin, V.: Hypothesis test for upper bound on the size of random defective set. IEEE International Symposium on Information Theory - Proceedings, 2017, 978-982 more…
  • Vorobyev, I.V.: Bounds on the rate of separating codes. Problems of Information Transmission 53 (1), 2017, 30-41 more…

2016

  • D′yachkov, A.G.; Vorobyev, I.V.; Polyanskii, N.A.; Shchukin, V.Yu.: On a hypergraph approach to multistage group testing problems. IEEE International Symposium on Information Theory - Proceedings 2016-August, 2016, 1183-1191 more…
  • D′yachkov, A.G.; Vorobyev, I.V.; Polyanskii, N.A.; Shchukin, V.Yu.: On multistage learning a hidden hypergraph. IEEE International Symposium on Information Theory - Proceedings 2016-August, 2016, 1178-1182 more…

2015

  • D'yachkov, A.G.; Vorobyev, I.V.; Polyansky, N.A.; Shchukin, V.Y.: Almost disjunctive list-decoding codes. Problems of Information Transmission 51 (2), 2015, 110-131 more…
  • D′yachkov, A.G.; Vorobyev, I.V.; Polyanskii, N.A.; Shchukin, V.Y.: Almost cover-free codes and designs. IEEE International Symposium on Information Theory - Proceedings 2015-June, 2015, 2899-2903 more…
  • D′yachkov, A.G.; Vorobyev, I.V.; Polyanskii, N.A.; Shchukin, V.Y.: Cover-free codes and separating system codes. IEEE International Symposium on Information Theory - Proceedings 2015-June, 2015, 2894-2898 more…
  • D′yachkov, A.G.; Vorobyev, I.V.; Polyanskii, N.A.; Shchukin, V.Y.: Symmetric disjunctive list-decoding codes. IEEE International Symposium on Information Theory - Proceedings 2015-June, 2015, 2236-2240 more…

2014

  • D′yachkov, A.G.; Vorobyev, I.V.; Polyanskii, N.A.; Shchukin, V.Yu.: Bounds on the rate of superimposed codes. IEEE International Symposium on Information Theory - Proceedings, 2014, 2341-2345 more…
  • D′yachkov, A.G.; Vorobyev, I.V.; Polyansky, N.A.; Shchukin, V.Y.: Bounds on the rate of disjunctive codes. Problems of Information Transmission 50 (1), 2014, 27-56 more…