CIF:Small: A Computationally-Enabled Rate Region Theory via Symmetry and Hierarchy

CIF:Small：通过对称性和层次结构计算的费率区域理论

基本信息

批准号：
1812965
负责人：
John Walsh
金额：
$ 32.5万
依托单位：
Drexel University
依托单位国家：
美国
项目类别：
Standard Grant
财政年份：
2018
资助国家：
美国
起止时间：
2018-10-01 至 2022-09-30
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=1812965&HistoricalAwards=false
关键词：
CIF Small Computationally Enabled Rate

项目摘要

Three timely applied engineering problems - limiting delay in communications for streaming media and remote control, coding information in data centers, and squeezing more capacity out of wireless and wired networks - all have fundamental limits that are dictated by a common family of underlying abstract rate region problems in information theory and coding. The underlying goal of this project is to advance the method of solution for these information theoretic rate region problems into the modern results-oriented data-driven massive computation age. Humans no longer tally large balance sheets, lay out massive integrated circuits, factor matrices, or solve linear programs by hand. Instead, we have recognized that computers are far better suited to doing these things both accurately and rapidly. This project will demonstrate that determining the coding rate regions that dictate the key design tradeoffs in these applied problems is a problem that is also best solved with computational methods. The research work to be carried out will enable the algorithms and software the PI has developed to reach larger instances of these problems by exploiting advanced notions of symmetry. Additionally, a hierarchical theory that enables complicated larger instances of these problems to be solved by combining computer generated solutions to simpler, smaller, constituents will be further developed.The abstract problems under study in this award are to determine the capacity regions of networks under network coding. Work under the project will proceed in three thrusts. The first thrust will show with specific worked examples and driver routines in software, how limits in distributed information storage systems, coded protocols for limited delay streaming media and remote control over multipath routed networks, and squeezing extra capacity out of wireless and wired communications networks, all can be formulated as abstracted network coding problems. The second thrust will utilize novel notions of symmetry of polyhedra to push algorithms and software the PI has developed to determine network coding capacity regions to as large problems as possible. The third thrust advances a structural theory enabling capacity regions of large networks to be inferred through simple computations combining carefully selected constituent networks. Throughout the project, care will be taken to illustrate the ideas by showing how to reduce the applied engineering design problems to a form that the algorithms and software that will be developed can solve.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.

三个及时应用的工程问题——限制流媒体和远程控制的通信延迟、数据中心中的信息编码以及从无线和有线网络中挤出更多容量——所有这些都具有由底层抽象速率区域的共同系列决定的基本限制信息论和编码中的问题。该项目的根本目标是将这些信息论速率区域问题的解决方法推进到现代结果导向的数据驱动的大规模计算时代。人类不再计算大型资产负债表、布置大规模集成电路、因子矩阵或手动求解线性程序。相反，我们已经认识到计算机更适合准确而快速地完成这些事情。该项目将证明，确定决定这些应用问题中关键设计权衡的编码率区域也是一个最好通过计算方法解决的问题。即将开展的研究工作将使 PI 开发的算法和软件能够利用先进的对称概念来解决这些问题的更大实例。此外，将进一步发展一种分层理论，通过将计算机生成的解决方案与更简单、更小的组成部分相结合，能够解决这些问题的复杂较大实例。该奖项正在研究的抽象问题是确定网络下网络的容量区域编码。该项目的工作将分三个重点进行。第一个重点将通过软件中的具体工作示例和驱动程序例程来展示分布式信息存储系统的限制、有限延迟流媒体的编码协议和多路径路由网络的远程控制，以及如何从无线和有线通信网络中挤出额外的容量，所有这些都可以表述为抽象的网络编码问题。第二个推动力将利用多面体对称性的新概念来推动 PI 开发的算法和软件，以确定尽可能大的问题的网络编码容量区域。第三个推动力提出了一种结构理论，使大型网络的容量区域能够通过结合精心选择的组成网络的简单计算来推断。在整个项目中，将通过展示如何将应用的工程设计问题简化为将要开发的算法和软件可以解决的形式来说明这些想法。该奖项反映了 NSF 的法定使命，并被认为值得支持通过使用基金会的智力优点和更广泛的影响审查标准进行评估。