A Caltech Library Service

A Study of Communication Networks through the Lens of Reduction


Wong, Ming Fai (2017) A Study of Communication Networks through the Lens of Reduction. Dissertation (Ph.D.), California Institute of Technology. doi:10.7907/Z9348HFK.


A central goal of information theory is to characterize the capacity regions of communication networks. Due to the difficulty of the general problem, research is primarily focused on families of problems defined by various classifiers. These classifiers include the channel transition function (i.e., noisy, deterministic, network coding), demand type (i.e., single-source, 2-unicast), network topology (i.e. acyclic network coding, index coding). To date, the families of networks that are fully solved remain limited. Moreover, results derived for one specific family often do not extend easily to other families of problems.

Our work shifts from the traditional focus on solving example networks to one that builds connections between problem solutions so that we can say where and when solving a problem in one domain would also solve a corresponding problem in another domain. Central to our approach is a technique called "reduction", in which we connect the solutions and results of communication problems. We say that problem A reduces to problem B when A can be solved by first transforming it to B and then applying a solution for B. We focus on two notions of reduction: reduction in code design and reduction in capacity region.

Our central results demonstrate reductions with respect to a variety of classifiers. We show that finding multiple multicast network capacity regions reduces to finding multiple unicast network capacity regions both when capacity is defined as the maximal rate over all possible codes and when capacity is defined as the optimal rate over linear codes. As a corollary to this result, we show that the same capacity reduction holds for when network types are limited to either network coding networks or index coding networks. In several instances, we show that a reduction in code design extends to a reduction in capacity region if and only if the edge removal conjecture holds. Here, the edge removal conjecture states that removing an edge of negligible capacity from a network does not change its capacity region.

One of the key challenges in network coding research is how to handle networks containing cycles. As a result, many papers on network coding restrict attention to acyclic networks and some results derived for acyclic networks do not extend to networks containing cycles. We consider a streaming model for network communication where information is streamed to its destination under a constraint on maximal delay at the decoder. Restricting our attention to this scenario enables us to prove a code reduction from network coding to index coding in both acyclic and cyclic networks. Since index coding networks are acyclic, a consequence of this reduction is that under the streaming model, there is no fundamental difference between acyclic and cyclic networks.

Item Type:Thesis (Dissertation (Ph.D.))
Subject Keywords:Information Theory; Network Coding; Index Coding
Degree Grantor:California Institute of Technology
Division:Engineering and Applied Science
Major Option:Electrical Engineering
Thesis Availability:Public (worldwide access)
Research Advisor(s):
  • Effros, Michelle
Thesis Committee:
  • Effros, Michelle (chair)
  • Low, Steven H.
  • Langberg, Michael
  • Bruck, Jehoshua
  • Umans, Christopher M.
Defense Date:24 May 2017
Non-Caltech Author Email:wongmingfai (AT)
Funding AgencyGrant Number
National Science Foundation1018741
National Science Foundation1321129
National Science Foundation1038578
National Science Foundation1527524
National Science Foundation1526771
Israel Science Foundation480/08
Record Number:CaltechTHESIS:06072017-154010713
Persistent URL:
Related URLs:
URLURL TypeDescription for Chapters 8 and 9. for Chapter 6. for Chapter 4. for Chapter 4. for Chapter 7.
Wong, Ming Fai0000-0002-9191-1277
Default Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:10311
Deposited By: Ming Fai Wong
Deposited On:08 Jun 2017 21:51
Last Modified:04 Oct 2019 00:16

Thesis Files

PDF - Final Version
See Usage Policy.


Repository Staff Only: item control page