NDLI: GROTESQUE: Noisy Group Testing (Quick and Efficient)

Content Provider	IEEE Xplore Digital Library
Author	Sheng Cai Jahangoshahi, M. Bakshi, M. Jaggi, S.
Copyright Year	2013
Description	Author affiliation: Chinese Univ. of Hong Kong, Hong Kong, China (Sheng Cai; Bakshi, M.; Jaggi, S.) \|\| Sharif Univ. of Technol., Tehran, Iran (Jahangoshahi, M.)
Abstract	Group-testing refers to the problem of identifying (with high probability) a (small) subset of D defectives from a (large) set of N items via a “small” number of “pooled” tests (i.e., tests have a positive outcome if even one of the items being tested in the pool is defective, else they have a negative outcome). For ease of presentation in this work we focus the regime when the number of defectives is sublinear, i.e., D = O $(N^{1-δ})$ for some δ > 0. The tests may be noiseless or noisy, and the testing procedure may be adaptive (the pool defining a test may depend on the outcome of a previous test), or non-adaptive (each test is performed independent of the outcome of other tests). A rich body of literature demonstrates that Θ(Dlog(N)) tests are information-theoretically necessary and sufficient for the group-testing problem, and provides algorithms that achieve this performance. However, it is only recently that reconstruction algorithms with computational complexity that is sub-linear in N have started being investigated (recent work by [1], [2], [3] gave some of the first such algorithms). In the scenario with adaptive tests with noisy outcomes, we present the first scheme that is simultaneously order-optimal (up to small constant factors) in both the number of tests and the decoding complexity (O(Dlog(N)) in both the performance metrics). The total number of stages of our adaptive algorithm is “small” (O(log(D))). Similarly, in the scenario with non-adaptive tests with noisy outcomes, we present the first scheme that is simultaneously near-optimal in both the number of tests and the decoding complexity (via an algorithm that requires O(Dlog(D) log(N)) tests and has a decoding complexity of O(D(logN + $log^{2}$ D)). Finally, we present an adaptive algorithm that only requires 2 stages, and for which both the number of tests and the decoding complexity scale as O(D(logN + $log^{2}$ D)). For all three settings the probability of error of our algorithms scales as O(1=(poly(D)).
Sponsorship	IEEE Cont. Syst. Soc.
Starting Page	1234
Ending Page	1241
File Size	1699412
Page Count	8
File Format	PDF
e-ISBN	9781479934102
DOI	10.1109/Allerton.2013.6736667
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2013-10-02
Publisher Place	USA
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Algorithm design and analysis Noise Adaptive algorithms Decoding Complexity theory Noise measurement Testing
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Non-adaptive probabilistic group testing with noisy measurements: Near-optimal bounds with efficient algorithms

GROTESQUE: Noisy Group Testing (Quick and Efficient) (2013)

Non-adaptive group testing: Explicit bounds and novel algorithms

GROTESQUE: Noisy Group Testing (Quick and Efficient)

Non-Adaptive Group Testing: Explicit Bounds and Novel Algorithms

Non-adaptive group testing with inhibitors

GBCS: A two-step compressive sensing reconstruction based on group testing and basis pursuit

Coding for noisy write-efficient memories

A variable breadth based adaptive tree search algorithm for MIMO systems

GROTESQUE: Noisy Group Testing (Quick and Efficient)

Similar Documents

Non-adaptive probabilistic group testing with noisy measurements: Near-optimal bounds with efficient algorithms

GROTESQUE: Noisy Group Testing (Quick and Efficient) (2013)

Non-adaptive group testing: Explicit bounds and novel algorithms

GROTESQUE: Noisy Group Testing (Quick and Efficient)

Non-Adaptive Group Testing: Explicit Bounds and Novel Algorithms

Non-adaptive group testing with inhibitors

GBCS: A two-step compressive sensing reconstruction based on group testing and basis pursuit

Coding for noisy write-efficient memories

A variable breadth based adaptive tree search algorithm for MIMO systems

GROTESQUE: Noisy Group Testing (Quick and Efficient)