A Tale of Two Channels

Broadcast channel and interference channel are two out of the four most fundamental multiuser communication scenarios (the other two being multiple access channel and relay channel). The capacity regions for the two settings, mentioned above, remains open. In this talk we will follow the recent attempts at understanding the relationships of the best known achievable regions and impossibility results with respect to the actual capacity region. The unifying theme of this talk is to describe some computational aspects of various regions characterized in terms of unions over auxiliary random variables.

This will be a whiteboard talk with the emphasis on the description of the lay of the land and a brief mention of some of the techniques involved; unless the audience steers the talk away from its intended course. No prior knowledge of the field will be required to follow the storyline. 

For those in search of open problems I will be describing some specific channel realizations (some of the simplest) whose capacity region remains undetermined. 

A good fraction of the talk will focus on the broadcast channel (for reasons that will become obvious) and in particular the computational aspects of Marton’s inner bound, the best known achievable region.