Publication
Finding theoretical limits on the performance of communication systems and designing schemes to achieve them is one of the fundamental questions in information theory. While the theory of point-to-point communication is well-investigated, most problems have remained unresolved when communication is over a multi-user system. This lack of understanding is unsatisfactory for today’s growing networks. Recently, significant progress has been made on these problems through a deterministic approach which lays out a promising path in developing a better understanding of multi-user communication systems and in devising new communication schemes. In this thesis, we take a deterministic approach to the problem of communicating nested message sets over wireless and wireline networks. This class of problems is motivated by its applications in video streaming services over heterogeneous networks, where users have different quality-of-service demands. This thesis mainly considers the scenario where a common message (e.g., the low resolution information of a video stream) and a private message (e.g., a higher level of resolution) are to be encoded into a signal and transmitted over a shared medium (e.g., mobile networks, the Internet) towards a set of users. A group of the users, called public receivers, demand only the common message and the rest, called private receivers, demand both messages. The focus is on single-hop broadcast channels and multi-hop wireline networks. A Linear deterministic model for broadcast channels assumes that every user receives a linear transformation of the sent signal. This model is mainly motivated by the MIMO Gaussian broadcast problem in the high SNR regime. We start our study with a simple, yet rich, class of such broadcast channels. We address the main challenges in designing optimal encoding schemes and seek new techniques. In particular, we give an exact characterization of the ultimate rates of communication (together with a class of linear codes that achieves them) over channels with three public and any number of private receivers. We show sub-optimality of these schemes for channels with more than three public receivers and propose a block Markov scheme which allows communication at higher rates. Using this technique, we characterize a set of achievable rates of communication. The intuitions and techniques that we develop over this class of channels guide us towards designing optimal codes for (general) linear deterministic channels. We fully characterize the set of all admissible rates of communication for linear deterministic channels with two public and any number of private receivers. We extend this result to also allow communication of three nested message sets. The study of deterministic models is aimed to be instructive for understanding more general channels. In this regard, we consider the problem of broadcasting two nested message sets over general broadcast channels with two public and one private receiver. Fo