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

Drexel University, Philadelphia PA

Investigators

Abstract

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.