Algorithms for Computing Limits on Information Flow and Storage in Networks

Multi-source Network Coding over Directed Acyclic Hypergraphs (HMSNC) is a general problem model which encompasses a variety of problems of practical interest, such as optimal information transfer across networks, efficient and reliable distributed storage of information, and the design of delay-mitigating codes for streaming. This thesis considers the design of computer programs for automatically proving achievability and converse theorems for rate regions of HMSNC instances. The traditional techniques for proving these theorems are based on human intuition, and are tedious at best. A computer-assisted theorem prover, albeit effective for small to moderate problem instances, is capable of rapidly producing thousands of proofs, which can then be analyzed to find patterns and make general statements about HMSNC, a problem which has proven difficult to solve in general. The first part of this thesis considers the design of an achievability prover for the HMSNC problem. Determining achievability of a specified rate vector for a given HMSNC instance, requires one to know an algorithm for determining if there exists an almost entropic polymatroid satisfying certain constraints on its rank function. Finding such an algorithm is a fundamental open problem in information theory, also called the problem of characterizing the closure of the region of entropic vectors ([gamma]*N , N [is an element of] N). A special case of this very difficult problem, called the Constrained Linear Representability Problem (CLRP) is defined, in the form of two variants: existential and enumerative. Algorithms based on group theoretic techniques for combinatorial generation are then developed to solve the enumerative variant of CLRP, which allows one to compute network coding rate regions achievable with a specified class of linear codes. The same algorithms are naturally able to solve the existential variant of CLRP, by halting as soon as the first combinatorial object satisfying the specified constraints is found, which allows them to determine the achievability of a specified rate vector with a specified class of linear codes. Thus, the first part of the thesis settles the problem of designing algorithms to compute achievable HMSNC rate regions, in the context of linear codes over a specified finite field. The second part of this thesis considers the problem of automating the converse proofs associated with the HMSNC problem. The tradiional approach to the converse proofs involves invocation of information inequalities one after another, to imply a specific inequality bounding the rate region of a given HMSNC instance. The only existing automation technique, is for verifying a putative inequality via linear programming, finding a collection of information inequalities such that a putative inequality bounding the HMSNC rate region can be obtained as their conic combination. However, no techniques exist to find the said putative inequalities bounding the rate region. To begin with, this thesis considers the problem of computing the tightest collection of linear inequalities bounding the rate region of a HMSNC instance, implied by a given collection of linear information inequalities which is called the problem of computing Explicit Polyhedral Outer Bounds (EPOBs) on the HMSNC rate regions. An algorithm based on a polyhedral projection technique, the Convex Hull Method (CHM), that is able to compute EPOBs exactly using rational arithmetic by working directly in the projection space is proposed. A variant of this algorithm, called symCHM, capable of reducing the complexity of computing EPOBs by exploiting problem symmetry, is also developed. The algorithms proposed in this thesis are implemented in form of two open-source software projects, the Information Theoretic Achievability Prover (ITAP) and the Information Theoretic Converse Prover (ITCP), which are both first of their kind tools. Computational experiments with a variety of interesting HMSNC instances are performed using ITAP and ITCP to gauge the practical performance of the algorithms developed. In addition to the HMSNC problem, the generality of the techniques developed in this thesis make them applicable to computer-assisted proofs in a plethora of related problems, viz. secret sharing, co-operative guessing games played on graphs, and quantum marginal scenarios.