Sparse Graph Codes for Nonadaptive Quantitative Group Testing This paper considers the problem of Quantitative Group Testing (QGT). Consider a set of N items among which K items are defective. The QGT problem is to identify (all or a sufficiently large fraction of) the defective items, where the result of a test reveals the number of defective items in the tested group. In this work, we propose a nonadaptive QGT scheme using sparse graph codes over biregular bipartite graphs and binary terrorcorrecting BCH codes. The proposed scheme provides exact recovery with probabilistic guarantee, i.e. recovers all the defective items with high probability. In particular, we show that for the sublinear regime where fracKN vanishes as K, Nrightarrowinfty, the proposed scheme requires at most mapprox 1.19Klog_2left(4.74fracNKright) tests to recover all the defective items with probability approaching one as K, Nrightarrowinfty. This bound can be achieved by t2. The testing and recovery algorithms of the proposed scheme for any tleq 4 have the computational complexity of Oleft(Klog2fracNKright) and Oleft(KlogfracNKright), respectively. Our simulation results also show that the proposed scheme significantly outperforms a nonadaptive semiquantitative group testing scheme recently proposed by Abdalla et at. in terms of the required number of tests for identifying all the defective items with high probability.

A FieldSize Independent Code Construction for Groupcast Index Coding Problems The length of an optimal scalar linear index code of a groupcast index coding problem is equal to the minrank of its sideinformation hypergraph. The sideinformation hypergraph becomes a sideinformation graph for a special class of groupcast index coding problems known as unicast index coding problems. The number of computations required to find the minrank of a sideinformation graph depends on the number of edges present in the sideinformation graph. In this paper, we define the notion of minrankcritical edges in a sideinformation graph and derive some properties of minrank, which identifies minranknoncritical edges. Using these properties we present a method to reduce the number of computations required to compute minrank. Apart from this, we give a heuristic method to compute minrank. Also, we give an heuristic algorithm to find a clique cover of the sideinformation graph by using some binary operations on the adjacency matrix of the sideinformation graph. We also give a method to convert a groupcast index coding problem into a single unicast index coding problem. Combining all these results, we give a method to construct index codes (with not necessarily optimal length) for groupcast index coding problems. The construction technique is independent of field size and hence can be used to construct index codes over the binary field. In some cases the constructed index codes are better than the best known in the literature both in terms of the length of the code and the minimum field size required.