Information Theory Seminar

TITLE: Information Flow over Wireless Networks: A Deterministic Approach

SPEAKER: David Tse (University of California at Berkeley)

DATE: 2:00 - 3:00 PM, Wednesday, September 3, 2008

LOCATION: Yosemite, 3L

ABSTRACT:
Characterizing how fast information can flow over networks is a long-standing problem. In a case of a single unicast flow over a wireline network, the solution is given by the classical max-flow min-cut theorem due to Ford-Fulkerson in 1956. This was extended to the multicast case by Ahlswede et al in 2000, which shows the surprising result that network coding is needed to achieve the min-cut bound. In this talk, we propose a parallel theory for wireless networks. Unlike wireline networks, signals transmitted from different nodes in a wireless network interact in a complex way due to the broadcast and superposition properties of the medium.

Our main contribution is a new deterministic channel model which captures these two properties but at the same time is more analytically tractable than the standard linear Gaussian channel model . We prove a max-flow min-cut theorem for networks with arbitrary number of nodes connected by this deterministic channel model, and lends evidence to the faithfulness of this model by showing that the scheme that achieves the min-cut bound can be naturally modified to design a scheme that approximately achieves the min-cut bound in the corresponding Gaussian network.

This talk requires minimal background in information theory.

Joint work with Salman Avestimehr at Berkeley and Suhas Diggavi at EPFL.

BIOGRAPHY:
David Tse received the B.A.Sc. degree in systems design engineering from University of Waterloo, Canada in 1989, and the M.S. and Ph.D. degrees in electrical engineering from Massachusetts Institute of Technology in 1991 and 1994 respectively. From 1994 to 1995, he was a postdoctoral member of technical staff at A.T. & T. Bell Laboratories. Since 1995, he has been at the Department of Electrical Engineering and Computer Sciences in the University of California at Berkeley, where he is currently a Professor.

He received a 1967 NSERC 4-year graduate fellowship from the government of Canada in 1989, a NSF CAREER award in 1998, the Best Paper Awards at the Infocom 1998 and Infocom 2001 conferences, the Erlang Prize in 2000 from the INFORMS Applied Probability Society, the IEEE Communications and Information Theory Society Joint Paper Award in 2001, and the Information Theory Society Paper Award in 2003.

He was the Technical Program co-chair of the International Symposium on Information Theory in 2004, and was an Associate Editor of the IEEE Transactions on Information Theory from 2001 to 2003. He is a coauthor, with Pramod Viswanath, of the text "Fundamentals of Wireless Communication". His research interests are in information theory, wireless communications and networking.