CRII: CIF: Next-Generation Group Testing for Neighbor Discovery in the IoT via Sparse-Graph Codes

群体测试是一个基本的推理问题，旨在通过群体测试从更大的项目集合中检测出一组有缺陷的项目。分组测试在通信、计算机科学、机器学习、生物学和信号处理等不同领域有多种应用。分组测试的主要挑战是设计少量的测试，使缺陷项能够可靠地恢复，并使用低复杂度的解码算法有效地恢复缺陷项。该项目的目标是通过开发快速和接近最优的组测试方案来解决这两个挑战。该项目重点关注的应用领域是物联网（IoT）中的主动邻居发现。在物联网环境中，有大量的低能耗设备收集和传输信息。这种系统的主要挑战是使大量设备能够通过可扩展和低复杂性的随机访问方案进行通信。本项目通过设计基于组测试的大规模主动邻居发现协议来解决这一挑战。本研究的核心思想是从编码理论的角度来看待群测试问题，开发具有近最优样本复杂度（测试次数）和最优解码复杂度的恢复算法。这种编码理论方法的主要内容是：(i)基于稀疏图代码设计测试；（ii）开发一种基于剥离的快速解码器，具有亚线性计算复杂度，用于检测有缺陷的项目；（ii）利用现代编码理论的强大工具，如密度进化，以最大限度地减少算法的样本复杂性。作为一个具体应用，通过解决群测试理论中规模的基本挑战，提出的工作旨在开发大规模通信系统的主动用户检测方案。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

Group testing is a fundamental inference problem that aims to detect a set of defective items from a larger set of items via group tests. Group testing has a variety of applications in different fields including communications, computer science, machine learning, biology, and signal processing. The main challenges in group testing are to design a small number of tests such that the defective items can be reliably recovered, and to efficiently recover the defective items using a low-complexity decoding algorithm. The goal of this project is to address both challenges by developing fast and near-optimal group testing schemes. The application area that the project focuses on is active neighbor discovery in the Internet of Things (IoT). In an IoT setting, there is an abundance of low-energy devices that collect and transmit information. The main challenge in such systems is to enable a massive number of devices to communicate via a scalable and low-complexity random access scheme. This project addresses this challenge by designing large-scale active neighbor discovery protocols based on group testing.The key idea of this research is to view the group testing problem from a coding-theoretic lens to develop recovery algorithms with near-optimal sample complexity (number of tests) and optimal decoding complexity. The main ingredients of this coding-theoretic approach are to: (i) design the tests based on a sparse-graph code; (ii) develop a fast peeling-based decoder with sublinear computational complexity for detecting the defective items; and (ii) leverage powerful tools from modern coding theory such as density evolution to minimize the sample complexity of the algorithm. As a concrete application, by addressing the fundamental challenge of scale in the theory of group testing, the proposed work aims to develop active user detection schemes for large-scale communication systems.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.