Network information theory deals with fundamental characterizations of information flow and/or compression over communication networks. While there are some satisfying characterizations for flows on networks represented as graphs, there have been few complete characterizations for networks with more complicated interactions such as those encountered in wireless networks. Given this discouraging state of affairs, a natural question to ask is whether there are methodologies to make progress on these questions.
In this talk we posit that one could gain insight into these problems by asking for less, i.e., by looking for (provable) approximate characterizations. By looking for approximate characterizations, one can obtain results for more general problems, with the hope that in terms of engineering solutions, these might actually be enough. Underlying these approximations are exact results for deterministic/lossless network communications.
We illustrate this approach by examining two problems. First is that of information flow over wireless Gaussian relay networks, where we show that the achievable rate is within a constant number of bits from the information-theoretic cut-set upper bound on the capacity of these networks. This constant depends on the topology of the network, but not the values of the channel gains. Underlying this is an exact characterization of a deterministic relay network. The second is the approximate characterization of the K-description Gaussian multiple description source coding problem. Here we show that the rate region can be sandwiched between two polytopes with matching hyperplanes, separated by a constant number of bits as well. Underlying this result is an exact characterization of a lossless multi-level source coding problem.
These results show that characterizations, within a constant number of bits approximation, may be a promising direction to get insight in network information theory problems.
Parts of this talk are joint work with S. Avestimehr (Berkeley), S. Mohajer (EPFL), C. Tian (AT&T) and D. Tse (Berkeley).
BiographyFrom Fall 1998 to July 2003, he was a principal member of technical staff at the Information Sciences Center at AT&T Shannon Laboratory. Since then he has joined the faculty of the School of Computer and Communication Sciences at EPFL. His research interests are in wireless ad hoc and sensor networks, information theory and data compression.
He has received the Ph.D. degree from Information Systems Laboratory, Department of Electrical Engineering, Stanford University in 1998.
He is a recipient of the 2006 IEEE Donald Fink prize paper award, the 2005 John Wiley & Sons IEEE Vehicular Technology Conference best paper award and the Okawa foundation research award.