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

CIF：小型：通信高效计算网络的通用构建块 - 基本限制

• 批准号: 2221379
• 负责人: Syed Jafar
• 金额: $ 60万
• 依托单位: University of California-Irvine
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2023
• 资助国家: 美国
• 起止时间: 2023-01-01 至 2025-12-31
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2221379&HistoricalAwards=false
• 关键词: CIF; Small; Generic; Building; Blocks

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.

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

项目成果

On the Capacity of Secure K -User Product Computation Over a Quantum MAC

量子MAC上安全K用户乘积计算能力

• DOI: 10.1109/lcomm.2023.3311368
• 发表时间: 2023-10
• 期刊: IEEE Communications Letters
• 作者: Lu, Yuxiang;Yao, Yuhang;Jafar, Syed A.
• 通讯作者: Jafar, Syed A.

The Generic Capacity of K User Symmetric Linear Computation Broadcast

K用户对称线性计算广播的通用容量

• DOI: 10.1109/icc45041.2023.10278932
• 发表时间: 2023-05
• 期刊: IEEE
• 作者: Yao, Yuhang;Jafar, Syed A.
• 通讯作者: Jafar, Syed A.