Columbia University Joint CS/EE Networking Seminar Series

Polar Codes and Power Blackouts

Prof. Edmund Yeh

Department of Electrical Engineering, Computer Science, and Statistics, Yale University

Tuesday, May 3, 10:30-11:30AM, CEPSR 414

Abstract: 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. Whereas a number of practical coding constructions (e.g. Turbo and Low Density Parity Check codes) can empirically approach the capacity of single-user communication channels, there is still a shortage of good practical coding schemes for multi-user communication 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 electrical power networks, cascading failure associated with power blackouts often result from a small number of initial line failures triggering a global failure event affecting the whole network, inflicting enormous socioeconomic cost. In spite of the increasing frequency of blackout events, there is still a shortage of understanding regarding the structures and properties which lend the network susceptible to cascading failure. In the second part of the talk, we show how the theory of percolation can be used to analyze the problem of cascading failure from a network perspective. For large-scale networks modeled by random geometric graphs, we use a simple but descriptive model to show that the cascading failure problem is equivalent to a dependent percolation process. Within this context, we obtain analytical conditions for the occurrence and non-occurrence of cascading failure, respectively.

Joint work with Eren Sasoglu, Emre Telatar, Zhenning Kong, and Hongda Xiao.

Speaker Biography: 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 in 2001. He is currently an Associate Professor of Electrical Engineering, Computer Science, and Statistics at Yale University.
Professor Yeh is the recipient of a Humboldt Research Fellowship, an 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 member of Phi Beta Kappa and Tau Beta Pi.