Polar Codes and Pricing via Quantization

Electrical and Computer Engineering
NYU Community Event

Speaker: Edmund Yeh

Host Faculty: Professor Elza Erkip


Achieving the fundamental capacity limits of noisy communication channels with low complexity coding schemes has been a major challenge for over 60 years. Recently, a new coding construction, called polar coding, has been shown to provably achieve the capacity of discrete memoryless single-user channels. In the first part of the talk, we extend the polar coding method to two-user multiple-access communication channels. We show that if the two users use the channel combining and splitting construction, the resulting multiple-access channels will polarize to one of five possible extremals, on each of which uncoded transmission is optimal. Our coding technique can achieve some of the optimal transmission rate pairs obtained with uniformly distributed inputs. The encoding and decoding complexity of the code is O(n log n) with n being the block length, and the block error probability is roughly O(2^{-\sqrt{n}}). Our coding construction is one of the first low-complexity coding schemes which have been proved to achieve capacity in multi-user communication networks.

In the second part of the talk, we apply concepts from information theory to solve a canonical nonlinear pricing problem in microeconomics with information constraints. Here, a seller offers a menu with a finite number n of choices to a continuum of buyers with a continuum of possible valuations. By revealing an underlying connection to quantization theory, we present the necessary conditions that the optimal finite menus for the socially efficient and for the revenue-maximizing mechanism, respectively, must satisfy. In both cases, we show that the loss resulting from using the n-class finite menu converges to zero at a rate proportional to 1/n^2 as n becomes large. We then extend our nonlinear pricing model to the multi-product environment, where vector quantization can be used to jointly designing finite menus in multiple dimensions.

Join work with Eren Sasoglu (UCSD), Emre Telatar (EPFL), Dirk Bergemann (Yale), Yun Xu (Yale), and Ji Shen (London School of Economics)

About the Speaker

Edmund Yeh received his B.S. in Electrical Engineering with Distinction from Stanford University in 1994, his M.Phil in Engineering from the University of Cambridge in 1995, and his Ph.D. in Electrical Engineering and Computer Science from MIT under Professor Robert Gallager in 2001. Since July 2011, he has been Associate Professor of Electrical and Computer Engineering at Northeastern University. Previously, he was Assistant and Associate Professor of Electrical Engineering, Computer Science, and Statistics at Yale University. He has held visiting positions at MIT, Princeton, University of California at Berkeley, Swiss Federal Institute of Technology Lausanne (EPFL), and Technical University of Munich.

Professor Yeh is the recipient of the Alexander von Humboldt Research Fellowship, the Army Research Office Young Investigator Award, the Winston Churchill Scholarship, the National Science Foundation and Office of Naval Research Graduate Fellowships, the Barry M. Goldwater Scholarship, the Frederick Emmons Terman Engineering Scholastic Award, and the President's Award for Academic Excellence (Stanford University). He is a Senior Member of the IEEE, a member of Phi Beta Kappa and Tau Beta Pi. He received the Best Paper Award at the IEEE International Conference on Ubiquitous and Future Networks (ICUFN), Phuket, Thailand, July 2012. Professor Yeh serves as the Secretary of the Board of Governors of the IEEE Information Theory Society.