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

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

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.