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

点击翻译按钮获取中文摘要

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.