Information Theory, Geometry, and Cover's Open Problem

Xiugang Wu
Postdoctoral fellow, Stanford
Date: Feb. 24th, 2017


Formulating the problem of determining the communication capacity of point-to-point channels as a problem in high-dimensional geometry is one of Shannon's most important insights that has led to the conception of information theory. However, such geometric insights have been limited to the point-to-point case, and have not been effectively utilized to attack network problems. In this talk, we present our recent work which develops a geometric approach to make progress on one of the central problems in network information theory, namely the capacity of the relay channel. In particular, consider a memoryless relay channel, where the channel from the relay to the destination is an isolated bit pipe of capacity C0. Let C(C0) denote the capacity of this channel as a function of C0. What is the critical value of C0 such that C(C0) first equals C(infinity)? This is a long-standing open problem posed by Cover and named ``The Capacity of the Relay Channel,'' in Open Problems in Communication and Computation, Springer-Verlag, 1987. In this talk, we answer this question in the Gaussian case and show that C0 can not equal to C(infinity) unless C0=infinity, regardless of the SNR of the Gaussian channels, while the cut-set bound would suggest that C(infinity) can be achieved at finite C0. The key step in our proof is a strengthening of the isoperimetric inequality on a high-dimensional sphere, which we use to develop a packing argument on a spherical cap that resembles Shannon's sphere packing idea for point-to-point channels.

Joint work with Leighton Barnes and Ayfer Ozgur.


Xiugang Wu is a postdoctoral fellow in the Department of Electrical Engineering at Stanford University. He received the B.Eng. degree in electronics and information engineering from Tongji University, Shanghai, China, in 2007, and the M.A.Sc. and Ph.D. degrees in electrical and computer engineering from the University of Waterloo, Waterloo, Ontario, Canada, in 2009 and 2014 respectively. His research interests are in information theory and wireless networks.