A New Algorithm for Two-Stage Group Testing

Ilya Vorobyev

    Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

    1 Citation (Scopus)

    Abstract

    Group testing is a well-known search problem that consists in detecting of s defective members of a set of t samples by carrying out tests on properly chosen subsets of samples. In classical group testing the goal is to find all defective elements by using the minimal possible number of tests in the worst case. In this work, two-stage group testing is considered. Using the hypergraph approach we design a new search algorithm, which allows improving the known results for fixed s and t→ ∞. For the case s = 2 this algorithm achieves information-theoretic lower bound 2 log2 t(1+o(1)) on the number of tests in the worst case. Also, the problem of finding m out of s defectives is considered.

    Original languageEnglish
    Title of host publication2019 IEEE International Symposium on Information Theory, ISIT 2019 - Proceedings
    PublisherInstitute of Electrical and Electronics Engineers Inc.
    Pages101-105
    Number of pages5
    ISBN (Electronic)9781538692912
    DOIs
    Publication statusPublished - Jul 2019
    Event2019 IEEE International Symposium on Information Theory, ISIT 2019 - Paris, France
    Duration: 7 Jul 201912 Jul 2019

    Publication series

    NameIEEE International Symposium on Information Theory - Proceedings
    Volume2019-July
    ISSN (Print)2157-8095

    Conference

    Conference2019 IEEE International Symposium on Information Theory, ISIT 2019
    Country/TerritoryFrance
    CityParis
    Period7/07/1912/07/19

    Fingerprint

    Dive into the research topics of 'A New Algorithm for Two-Stage Group Testing'. Together they form a unique fingerprint.

    Cite this