A Computationally Informed Hierarchical Theory of Network Coding Rate Regions

The optimization of codes for multiple engineered systems, including those for caching content, streaming multimedia, making the best use of a network of communication links, and cloud information storage, admits a common mathematical formulation. This common formulation is to determine the capacity region of an abstracted “network”- a labeled hypergraph that is determined from the original problem’s constraints. Determining the capacity regions of every possible network under network coding has been shown, in turn, to enable the exhaustive solution of a surprisingly diverse collection of fundamental mathematical problems. These include determining all implications among conditional independences of random variables, the expressive power of graphical models in machine learning, the laws of information theory, and all inequalities linking the sizes of subgroups of a common finite group.

In view of their importance, this talk details a computationally enabled theory of network coding capacity regions. First, the process of proving a network coding capacity region for a given network, which is typically done with hours of intense human intuition and effort, is formulated as a series of algorithms. These algorithms are constructed using tools from linear programming as well as methods from abstract algebra for exhaustively listing discrete structures that are inequivalent under symmetry. These methods and their implementations are capable of exhaustively generating the capacity regions, and their proofs, of all networks up to a given size. These methods have enabled a database of roughly 1 million equivalence classes of small network coding capacity regions to be generated, but have complexity which grows rapidly with the size of the network.

In order to learn information about networks at scale from this massive database of small problems, a structural theory, inspired by the notion of forbidden minors for families of graphs and matroids, is then devised. This hierarchical theory involves the creation of embedding operators, which show how rate regions of certain small networks are implied by those of a large network, and combination operators, which combine rate regions of small networks to obtain rate regions of a large one. A recently proposed combination operator for pasting intermediate edges and sinks of one network to sources of another based on an information theoretic notion of common information is presented. Using both combination and embedding operators, even a small seed database of capacity regions of small networks can be used to prove capacity regions for an unbounded number of arbitrarily large networks.