Abstract

This monograph illustrates a novel approach, which is based on changing the focus to seek approximate solutions accompanied by universal guarantees on the gap to optimality, in order to enable progress on several key open problems in network information theory. We seek universal guarantees that are independent of problem parameters, but perhaps dependent on the problem structure. At the heart of this approach is the development of simple, deterministic models that capture the main features of information sources and communication channels, and are utilized to approximate more complex models. The program advocated in this monograph is to use first seek solutions for the simplified deterministic model and use the insights and the solution of the simplified model to connect it to the original problem. The goal of this deterministic-approximation approach is to obtain universal approximate characterizations of the original channel capacity region and source coding rate regions. The translation of the insights from the deterministic framework to the original problem might need non-trivial steps either in the coding scheme or in the outer bounds. The applications of this deterministic approximation approach are demonstrated in four central problems, namely unicast/multicast relay networks, interference channels, multiple descriptions source coding, and joint source-channel coding over networks. For each of these problems, it is illustrated how the proposed approach can be utilized to approximate the solution and draw engineering insights. Throughout the monograph, many extensions and future directions are addressed, and several open problems are presented in each chapter. The monograph is concluded by illustrating other deterministic models that can be utilized to obtain tighter approximation results, and discussing some recent developments on utilization of deterministic models in multi-flow multi-hop wireless networks.

An Approximation Approach to Network Information Theory

The interaction between communication entities, which is unique in the network setting, have been at the root of many difficult challenges in communications and information theory. This monograph advocates a sequential approach to make progress on the network communication problem. In order to do this, the channel (and source) model to capture the essence of the network communication problem are simplified and connected to the original problem. This leads to the concept of approximate characterizations of the channel capacity region and source coding rate regions.

Approximate solutions to information theory problems are not new. However, they are by and far isolated results each with its own proof technique. This monograph describes a breakthrough systematic approach with two levels of approximation that can be applied to many problems. It concludes by demonstrating its application to four central problems in network information theory: (1) Relay networks, (2) Interference channels, (3) Multiple descriptions problem, and (4) Joint source-channel coding over networks.

This monograph is intended for researchers and graduate students working at the forefront of research into network and communications problems.