<script type="text/javascript">
<!--
document.write('<div id="oa_widget"></div>');
document.write('<script type="text/javascript" src="https://www.openaire.eu/index.php?option=com_openaire&view=widget&format=raw&projectId=undefined&type=result"></script>');
-->
</script>
In combinatorial group testing (CGT), the objective is to identify the set of at most $d$ defective items from a pool of $n$ items using as few tests as possible. The celebrated result for the CGT problem is that the number of tests $t$ can be made logarithmic in $n$ when $d=O(poly(\log n))$. However, state-of-the-art GT codes require the items to be tested $w=��(d\log n)$ times and tests to include $��=��(n/d)$ items (within log factors). In many applications, items can only participate in a limited number of tests and tests are constrained to include a limited number of items. In this paper, we study the "sparse" regime for the group testing problem where we restrict the number of tests each item can participate in by $w_{\max}$ or the number of items each test can include by $��_{\max}$ in both noiseless and noisy settings. These constraints lead to an unexplored regime where $t$ is a fractional power of $n$. Our results characterize the number of tests $t$ as a function of $w_{\max} (��_{\max})$ and show, for example, that $t$ decreases drastically when $w_{\max}$ is increased beyond a bare minimum. In particular, if $w_{\max}\leq d$, then we must have $t=n$, i.e., individual testing is optimal. We show that if $w_{\max}=d+1$, this decreases suddenly to $t=��(d\sqrt{n})$. The order-optimal construction is obtained via a modification of the Kautz-Singleton construction, which is known to be suboptimal for the classical GT problem. For more general case, when $w_{\max}=ld+1$ for $l>1$, the modified K-S construction requires $t=��(d n^{\frac{1}{l+1}})$ tests, which we prove to be near order-optimal. We show that our constructions have a favorable encoding and decoding complexity. We finally discuss an application of our results to the construction of energy-limited random access schemes for IoT networks, which provided the initial motivation for our work.
FOS: Computer and information sciences, Computer Science - Information Theory, Information Theory (cs.IT)
FOS: Computer and information sciences, Computer Science - Information Theory, Information Theory (cs.IT)
citations This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 14 | |
popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Top 10% | |
influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Top 10% |