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中研究线性计算广播网络的容量。其次是对推力2中的线性计算多访问网络的研究。推力2还探讨了如何将这些构建块组合到许多与Many/MultiHop Computation网络中。该范围在推力3中扩展到整数和某些非线性计算类别的线性计算。要克服的关键障碍是，这些构件包含众所周知的硬性问题，例如特殊情况，例如，索引编码是计算广播的一种特殊情况。来自通用案例复杂性领域中无线网络和相似之处的自由度研究的见解表明，尽管一般问题（包括所有情况）至少与最困难的情况一样困难，但通用问题（几乎包括所有情况）是可以更加宽松的。因此，为了寻找一个有凝聚力的理论，该项目将重点放在通用设置作为其起点上，随后扩展了对更难的实例，以提高对通用案例的理解。凝聚力理论建立在与先前对无线网络的研究中有用的联系的基础上，例如子空间一致性链，二元性，空间规模不变性，集群不等式，维度分析，维度分析以及各种干预统一方案。这种奖项反映了NSF的法定任务和综述的范围，这是通过评估的范围来评估的。