CIF: Small: Generic Building Blocks of Communication-efficient Computation Networks - Fundamental Limits

随着未来10年内联网设备的数量预计将达到人口的近60倍，通信网络将越来越多地用于计算任务。沿着连接设备的计算能力，这些“计算网络”潜力的关键决定因素将是其通信效率的基本限制。这给计算网络容量的研究带来了紧迫感，这是本项目的主要动机。使这些网络特别有趣的是，机器通信，由于其算法特性，创建了可预测的依赖关系和辅助信息结构，可以以原则性的方式利用这些结构来提高通信效率。计算网络的容量限制在很大程度上是未知的。即使是基本的构建块-计算广播和多路访问网络-也是如此，这些构建块对于许多推动计算网络兴趣的应用程序至关重要，例如编码缓存，私有信息检索，分布式存储修复，联邦学习和共享虚拟现实。通过研究这些构建模块的能力，该项目为计算网络的内聚信息理论奠定了基础。从线性有限域设置开始，线性计算广播网络的容量首先在推力1中研究。其次是推力2中的线性计算多址网络的研究。推力2还探讨了如何将这些构建块组合成多对多/多跳计算网络。在第3章中，范围扩展到整数上的线性计算和某些非线性计算。要克服的一个关键障碍是，这些构建块包含作为特殊情况的公认的难题，例如，索引编码是计算广播的特殊情况。从无线网络的自由度研究和一般情况复杂性领域的类似研究中得出的见解表明，虽然一般问题（包括所有情况）必然至少与最难的情况一样难，但一般问题（包括几乎所有情况）更容易处理。因此，为了寻找一种内聚理论，该项目侧重于作为起点的通用设置，随后在对通用情况的更好理解的指导下扩展到更难的实例。内聚理论建立在与无线网络先前研究中有用的思想的联系之上，如子空间对齐链、对偶性、空间尺度不变性、和集不等式、维数分析和各种干扰对齐方案。该奖项反映了NSF的法定使命，并通过使用基金会的智力价值和更广泛的影响审查标准进行评估，被认为值得支持。

With the number of connected devices projected to reach nearly 60 times the human population within the next 10 years, communication networks will increasingly be used for computation tasks. Along with the computing capabilities of the connected devices, a key determinant of the potential of these "computation networks" will be the fundamental limit of their communication efficiency. This lends a sense of urgency to the study of the capacity of computation networks, the prime motivation of this project. What makes these networks particularly intriguing is that machine communication, because of its algorithmic character, creates predictable structures of dependencies and side information, which may be exploited in principled ways towards improvements in communication efficiency. The capacity limits of computation networks are largely unknown. This is the case even for the basic building blocks — computational broadcast and multiple-access networks — that are essential to many of the applications driving interest in computation networks, such as coded caching, private information retrieval, distributed storage repair, federated learning, and shared virtual reality. By studying the capacity of these building blocks, this project lays the foundation for a cohesive information theory of computation networks.The project is organized into three thrusts. Starting with linear finite-field settings, the capacity of linear computation broadcast networks is studied first in Thrust 1. This is followed by the study of the linear computation multiple-access networks in Thrust 2. Thrust 2 also explores how these building blocks may be combined into many-to-many/multihop computation networks. The scope is expanded in Thrust 3 to linear computations over integers and to certain classes of non-linear computations. A key obstacle to overcome is that these building blocks contain well recognized hard problems as special cases, e.g., index coding is a special case of computation broadcast. Insights from degrees-of-freedom studies of wireless networks and parallels in the field of generic-case complexity suggest that while the general problem (which includes all cases) is necessarily at least as hard as its hardest instances, the generic problem (which includes almost-all cases) is much more tractable. In search of a cohesive theory, the project therefore focuses on the generic settings as its starting points, with subsequent expansion towards the harder instances guided by the improved understanding of generic cases. The cohesive theory builds upon connections to ideas that have been useful in prior studies of wireless networks, like subspace-alignment chains, duality, spatial scale invariance, sumset inequalities, dimensional analysis, and a variety of interference alignment schemes.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.