2009 ISIT Plenary Lecture
It's Easier to Approximate
Professor David Tse
University of California, Berkeley
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.