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

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

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.