Sublinear decoding schemes for non-adaptive group testing with inhibitors
share
Identification of up to d defective items and up to h inhibitors in a set of n items is the main task of non-adaptive group testing with inhibitors. To efficiently reduce the cost of this Herculean task, a subset of the n items is formed and then tested, i.e., group testing. A test outcome is positive if it contains at least one defective item and no inhibitors, and negative otherwise. We present two decoding schemes for efficiently identifying the defective items and the inhibitors in the presence of e erroneous outcomes in time poly(d, h, e, n), which is sublinear to the number of items n. This decoding complexity significantly improves the state-of-the-art schemes in which the decoding time is linear to the number of items n, i.e., poly(d, h, e, n). Moreover, each column of the measurement matrices associated with the proposed schemes can be nonrandomly generated in time polynomial of the number of rows. As a result, one saves space for storing them.
READ FULL TEXT