Dr. John Walsh
This dissertation utilizes computation tools to solve an important open problem in information theory and network coding, that is, to calculate the rate regions of multi-source multi-sink networks. For enumeration purpose, notions of minima networks and network equivalence are defined. Then efficient enumeration algorithms, based on list of Sperner families and Leiterspiel algorithm, are developed, where the algorithm based on Leiterspiel outer performs the former one. With the enumeration tools, millions of non-isomorphic networks are enumerated and most of them are solved by our computation software. To analyze the huge repository of rate regions, operators that relate networks of different sizes are defined so that more large networks can be solved and forbidden network minors regarding some classes of linear codes can be obtained. This dissertation contains two major chapters, where Chapter 2 focuses on multi-level diversity coding systems (MDCS), a special class of multi-source networks, and Chapter 3 extends the discussion to the general multi-source multi-sink hyperedge networks with more powerful hierarchy structure developed.
In Chapter 2, the rate regions of multilevel diversity coding systems (MDCS), a sub-class of the broader family of multi-source multi-sink networks with special structure, are investigated. After showing how to enumerate all non-isomorphic MDCS instances of a given size, the Shannon outer bound and several achievable inner bounds based on linear codes are given for the rate region of each non-isomorphic instance. For thousands of MDCS instances, the bounds match, and hence exact rate regions are proven. Results gained from these computations are summarized in key statistics involving aspects such as the sufficiency of scalar binary codes, the necessary size of vector binary codes, etc. Also, it is shown how to generate computer aided human readable converse proofs, as well as how to construct the codes for an achievability proof. Based on this large repository of rate regions, a series of results about general MDCS cases that they inspired are introduced and proved. In particular, a series of embedding operations that preserve the property of sufficiency of scalar or vector codes are presented. The utility of these operations is demonstrated by boiling the thousands of MDCS instances for which binary scalar codes are insufficient down to 12 forbidden smallest embedded MDCS instances.
With the exciting rapid computations on MDCS problem, Chapter 3 investigates further to the enumeration, rate region computation, and hierarchy of general multi-source multi-sink hyperedge networks under network coding, which includes multiple network models, such as independent distributed storage systems and index coding problems as special cases. A notion of minimal networks and a notion of network equivalence under group action are defined. By harnessing the Leiterspiel algorithm, an efficient enumeration algorithm is presented. Using this algorithm, millions of non-isomorphic networks are obtained. Then by applying computational tools, exact rate regions of most of the obtained networks are calculated, leaving the rest with outer bounds and simple code achieving inner bounds. In order to better understand and analyze the huge repository of rate regions, several embedding (as extensions of embedding operations defined in Chapter 2) and combination operations are defined in a manner that rate region of the network after operation can be derived from the rate region of networks involved in the operation. The embedding operations enable us to obtain a list of forbidden network minors for the sufficiency of a class of linear codes. The combination operations enable us to solve large networks that can be obtained by combining some solvable networks. The integration of both embedding and combination operations is able to generate many more network capacity regions than can be obtained through combination operations alone.
