Appears in collection : Nexus Trimester - 2016 - Fundamental Inequalities and Lower Bounds Theme

This talk identifies a number of methods and algorithms we have created for determining fundamental rate regions and efficient codes for network coding problems, demonstrates their use via novel software tools we have implemented, then discusses a computationally oriented research agenda we have followed building on this capability. The ability to train a computer to calculate fundamental rate regions for network coding and computing problems, previously determined primarily by hand, inspires several new research directions, both algorithmic and theoretical. First of all, while conceptually well-posed, the process of directly computing certain polyhedral outer and inner bounds to rate regions has a complexity that grows very rapidly in the size of the network. In light of this, in order to enable the computer to solve as many networks and as large networks as possible, we define an appropriate notion of problem minimality, as well as notions of symmetry and equivalence formalized via the language of group actions. Even after accounting for these reductions that exploit the known problem symmetries, only somewhat small problems can be solved with the software tools. However, the variety in even these small problems is so great that one can rapidly generate lists of network coding problem equivalence classes far too vast for a human to exhaustively read and interpret. In order to learn from this combinatorial database, and to be able to harness it to understand networks at scale, we develop a structural theory inspired by the notion of graph and matroid minors. In particular, combination and embedding operators and associated theories are created that enable the rate region and its properties of a large network to be directly deduced from small networks which it contains. The embedding operators enable us to learn from the massive database of solved network coding problems by identifying small numbers of minimal forbidden network minors for sufficiency of certain classes of codes to exhaust the capacity region. Additionally, the combinations and embedding operators coupled with the database enable the solution of certain network coding problems of arbitrary size and scale.