David Tse: It's Easier to Approximate

• Report rights infringement
• published: 03 Mar 2016
• views: 390

2009 ISIT Plenary Lecture It's Easier to Approximate Professor David Tse University of California, Berkeley Abstract: Unique among many engineering fields, information theory aims for and almost demands exactly optimal solutions to infinite-dimensional design problems. Such a high standard was set by Shannon in his original analysis of point-to-point communication problems. After almost 40 years of effort, meeting such a standard has proved to be far more difficult when extending Shannon's theory to networks. In this talk, we argue that much broader progress can be made when instead one seeks approximate solutions with a guarantee on the gap to optimality. Focusing on the practically important models of linear Gaussian channels and Gaussian sources, our approach consists of three steps: 1) simplify the model; 2) obtain optimal solution for the simplified model; 3) translate the optimal scheme and outer bounds back to the original model.? We illustrate this approach on five long-standing open problems: 1) relay networks; 2) interference channels; 3) distributed source coding; 4) multiple description; 5) joint source-channel broadcasting. We give examples where this approach yields: 1) achievable schemes which are arbitrarily better than existing schemes; 2) outer bounds which are arbitrarily tighter than existing bounds; 3) occasionally exact results. This approach also shows a surprising connection between Gaussian problems and network coding problems on wired networks. 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 has given plenary talks at international conferences such as ICASSP in 2006, MobiCom in 2007 and CISS in 2008. 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".