Computation and Communication - Two sides of one tapestry?

October 30, 2009
Prof. Michael Gastpar


Networks have been studied in depth for the past several decades, but one feature has received little attention until recently: Interference.

There is, of course, a good reason for this: In classical networks such as supply chains and the wired internet, interference can be addressed in a near-optimal fashion via simple protocols that avoid it.

However, in the networks of prime interest today, such as wireless ad hoc networks, interference is often the dominant bottleneck and simply avoiding it entails major performance penalties. Therefore, the next important step is a thorough understanding of the nature of interference.

In this talk, we argue that interference can be understood as computation: Multiple input signals are garbled together to produce a certain output. This is nothing but a certain computation performed on the input signals, possibly subject to noise or other stochastic effects.

We show how this perspective inspires novel paradigms for thinking about communication in networks, including cooperation, "wireless network coding," and interference management. In particular, the computational perspective may help resolve the nagging question concerning the nature of information in networks: We have argued earlier that the "bit", a universal currency of information in single noisy channels, is inappropriate in general networks. A more appropriate currency of information could result from computational primitives, retaining algebraic structure as a fundamental property of information.

Joint work with Bobak Nazer, and in part with Jiening Zhan.


Michael Gastpar (Ph.D. EPFL, 2002, M.S. UIUC, 1999, Dipl. El-Ing, ETH,1997) is currently an Associate Professor in the Department of Electrical Engineering and Computer Sciences at the University of California, Berkeley. He was a visiting professor (2008/09) at the Technical University of Delft, The Netherlands. He was also a student in electrical engineering and philosophy at the Universities of Edinburgh and Lausanne, and a summer researcher in the Mathematics of Communications Department at Bell Labs, Lucent Technologies. His research interests are in network information theory and related coding and signal processing techniques, with applications to sensor networks and neuroscience. He won the 2002 EPFL Best Thesis Award, an NSF CAREER award in 2004, and an Okawa Foundation Research Grant in 2008.