Title: Non-convex optimization and multiuser information theory
Chandra Nair, The Chinese University of Hong Kong
Capacity regions in multiuser information theory were traditionally established using an achievability argument and a converse to corresponding rate regions. Recently, however, capacity regions have been established, for non-trivial and important classes of channels (such as additive Gaussian noise models and others), by optimizing functionals on probability spaces generated from inner or outer bounds and showing that the bounds match for these channels. Optimization ideas have also been used to determine if certain achievable regions proposed in the literature are optimal or sub-optimal in general. The study of these non-convex optimization problems required developing new insights and techniques. In this talk, I will outline the ideas involved in obtaining the results, as well as illustrate the relationship of these to problems of interest in related areas. I will present some unifying observations across the family of optimization problems that we have managed to solve, and state some elementary instances of similar problems whose solutions would be of immense interest.
Chandra Nair is an Associate Professor with the Information Engineering department at The Chinese University of Hong Kong. His research interests and contributions have been in developing ideas, tools, and techniques to tackle families of combinatorial and non-convex optimization problems arising primarily in the information sciences.
His recent research focus has been on studying the optimality of certain inner and outer bounds to capacity regions for fundamental problems in multiuser information theory. He, along with his doctoral student Yanlin Geng, received the 2016 Information Theory Society paper award for developing a novel way to establish the optimality of Gaussian distributions. A proof of the Parisi and Coppersmith-Sorkin conjectures in the Random Assignment Problem constituted his doctoral dissertation; and he resolved some conjectures related to Random Energy model approximation of the Number Partition Problem during his post-doctoral years.
Chandra Nair got his Bachelor’s degree, B.Tech(EE), from IIT Madras (India) where he was the Philips (India) and Siemens (India) award winner for the best academic performance. Subsequently he was a Stanford graduate fellow (00-04) and a Microsoft graduate fellow (04-05) during his graduate studies at the EE department of Stanford university. Later, he became a post-doctoral researcher (05-07) with the theory group at Microsoft Research, Redmond. He has been a faculty member of the information engineering department at The Chinese University of Hong Kong since Fall 2007. He was an associate editor for the IEEE Transactions on Information Theory (2014-2016) and is currently a distinguished lecturer of the IEEE Information theory society. He is a fellow of the IEEE. He serves as the Programme Director of the undergraduate program on Mathematics and Information Engineering and the Director of the Institute of Theoretical Computer Science and Communications.
Title: Past, Present, and Future of Polar Coding
Alexander Vardy, University of California at San Diego
Polar coding, invented by Arikan ten years ago, is one of the most original and profound developments in coding theory to date. We will not attempt to summarize 10 years of polar coding in one talk. Instead, we hope this talk will provide a glimpse into several topics curated from the past, present, and future of polar codes.
No prior knowledge of polar coding is assumed; we will begin with a brief tutorial on polarization theory and polar codes. We will then describe the list-decoding algorithm for polar codes, and how it is used in the 5G standard. We will also present our recent results on polar codes with large kernels. In particular, we will show that such codes not only approach capacity, but do so as fast as theoretically possible, at least on the binary erasure channel.
Alexander Vardy is the the Jack Keil Wolf Endowed Chair Professor at the University of California San Diego, where he is affiliated with the Department of Electrical Engineering and the Department of Computer Science. He was born in Moscow, U.S.S.R, and grew up in Israel. He graduated summa cum laude from the Technion – Israel Institute of Technology in 1985, and completed his Ph.D. in 1991 at the Tel Aviv University.
Since 1987, he has been working in the field of coding theory. As part of his work, he has discovered certain codes and decoding algorithms that are now named after him. His 2003 paper with Ralf Koetter on algebraic soft-decision decoding of Reed-Solomon codes won the IEEE Information Theory Society Paper Award, and the resulting decoding algorithm became known as the Koetter-Vardy decoder. In his 2005 paper with Farzad Parvaresh (FOCS Best Paper Award), he discovered the Parvaresh-Vardy codes. In his 2011 paper with Ido Tal (Communications & Information Theory Societies Joint Paper Award), he introduced CRC-aided list-decoding of polar codes that is currently used in the 5G wireless communications standard. He also holds the record for the densest packing of spheres in 20 dimensions and is a co-discoverer of the only known q-analogue of a Steiner system.