Approximation techniques in network information theory

Abstract

In the early years of information theory, Shannon and other pioneers in information theory set a high standard for future generations of information theorists by determining the exact fundamental limits in point-to-point communication and source coding problems. Extending their results to network information theory is important and challenging. Many problems in network information theory, such as characterizing the capacity regions for fundamental building blocks of a communication network, namely the broadcast channel, the interference channel and the relay channel, have been open problems for several decades. When exact solutions are elusive, progress can be made by seeking for approximate solutions first. The first contribution of the thesis is to obtain the approximate capacity region for the symmetric Gaussian interference channel in the presence of noisy feedback. The key approximation technique used to complete this task is the so-called {linear deterministic model}. It is found that when the feedback link strengths exceed certain thresholds, the performance of the interference channel starts to improve. The second contribution is on the understanding of the interference channel in the finite-blocklength regime. In the so-called strictly very strong interference regime, the {normal approximation} is used to obtain the approximate finite-blocklength fundamental limits of the Gaussian interference channel. It is found that, in this regime, the Gaussian interference still behaves like a pair of separate independent channels. The third contribution is a study of the finite-blocklength source coding problem with side information available at both the encoder and the decoder. It is found that the rate of convergence to the Shannon limit is governed by both the randomness of the information source and the randomness of the side information.