Princeton University

School of Engineering & Applied Science

William Pierson Field Lectures: Extremal distributions in network information theory: Part I: Discrete memoryless channel settings

Chandra Nair, The Chinese University of Hong Kong
Engineering Quadrangle B205
Monday, October 20, 2014 - 1:30pm to 3:00pm

Part I, Monday, October 20th: Discrete memoryless channel settings
Abstract: Multiterminal information theory is rife with open problems of central interest. Even among the multitude of open problems, determining the capacity regions for the discrete memoryless broadcast channel and the discrete memoryless interference channel, inarguably, represent two of the most fundamental unresolved instances. Indeed these two problems share another interesting fact: a region, due to Marton for the broadcast channel, and  another region due to Han and Kobayashi for the interference channel represent the best achievable rate regions for the two problems under any channel setting. It has been known that to test the optimality (or sub-optimality) of either of these two coding strategies, it suffices to compare the 1-letter region for a generic channel to its 2-letter counterpart.
Until recently, very little progress was made (or effort was spent) on trying to determine the optimality of either of these two coding strategies using the above observation. A possible difficulty of the above approach is to compute the actual achievable region yielded by the coding strategies as the achievable regions are expressed as the unions (over auxiliary random variables) of achievable regions for any given choice of auxiliary random variables. In the case of Marton’s achievable region, some of the auxiliary random variables did not even possess bounds on their cardinalities, thus making the region intractable to evaluate.
 In this tutorial, I will introduce the various ideas that have been used to identify and restrict the extremal distributions in discrete memoryless broadcast channels. In particular, I will start with Caratheodory’s theorem and an improvement on it due to Bunt. I will then proceed to recent ideas, namely the perturbation arguments (due to Amin Gohari and Venkat Anantharam) and arguments using concave envelopes.
<strong>Biography:</strong> Prof. Nair is an Associate professor with the department of Information Engineering at The Chinese University of Hong Kong. He received a Masters (2002) and PhD (2005) in electrical engineering from Stanford University. He was a Stanford Graduate Fellow (2000-2004) and then a Microsoft Graduate Fellow (2004-2005) during his graduate studies. Then he became a postdoctoral fellow at the (math) theory group in Microsoft Research for two years.
Prof. Nair did his undergraduate studies at the Indian Institute of Technology (IIT), Madras in electrical engineering graduating in 1999. He received the Siemens and Philips (India) medal for having the best academic record in the department during his undergraduate studies. Concurrently, he also completed the four year nurture programme in Mathematics at the Institute of Mathematical Sciences(IMSc ) under the auspices of the National Board of Higher Mathematics(NBHM). He ranked first in the Indian National Mathematics Olympiad in 1994.
His current interests are in basic network information theory problems. He has previously worked on problems touching many areas including combinatorial optimization, statistical physics, algorithms, and networks. He is currently serving as an associate editor for the IEEE Transactions on Information Theory.