How Physics & CS Helped us Build Better Codes - Rüdiger Urbanke - Lecture 1 (1/8) - July 2018

Scribe notes: https://www.ee.iitb.ac.in/jtg18/Urban...

JTG/IEEE IT Society Summer School on Information Theory, Signal Processing, Communications and Networks, IIT Bombay, 2-5 July, 2018
https://www.ee.iitb.ac.in/jtg18/

How Physics and Computer Science Helped us Build Better Codes - Prof. Rüdiger Urbanke, EPFL

Lecture 1 of 8

We use error correcting codes daily. The main reason that we might not be more aware of how much we depend on them is that they typically work quite well, ensuring that our daily communication works smoothly, and our stored data can be retrieved reliably.
Since the inception of coding theory in the mid 40s, many different concepts have been brought to bear to design good error correcting codes. Not surprisingly, many of these methods have their origin in mathematics. Sophisticated concepts rooted in algebra, number theory, geometry and probability have all been successfully applied to codes that have been implemented. But math is not the only discipline that has contributed to coding theory. I will discuss two perhaps slightly less obvious resources, namely physics and theoretical computer science.
Physics has given us spatially coupled codes. These use the same physical principle that is responsible for hail formation or chemical heat pads (good for skiing in winter). Properly-designed spatially coupled codes are universally capacity-achieving under low-complexity decoding.
The second inspiration comes from theoretical computer science, namely the fact that symmetric and monotone Boolean functions have sharp thresholds. This can be used to settle one of the oldest problems in coding theory i.e. "do Reed-Muller codes achieve capacity?"

Bio: Rüdiger L. Urbanke obtained his Dipl. Ing. degree from the Vienna University of Technology in 1990, and MSc and PhD in Electrical Engineering from Washington University in St. Louis in 1992 and 1995, respectively. He held a position at the Mathematics of Communications Department at Bell Labs from 1995 till 1999 before becoming a faculty member at the School of Computer & Communication Sciences (I&C) of EPFL. He is principally interested in the analysis and design of modern coding schemes, graphical models, and the application of methods from statistical physics to problems in communications. From 2000 to 2004 he was an Associate Editor of the IEEE Transactions on Information Theory. From 2009 till 2012 he was the head of the I&C Doctoral School and in 2013 he served as a Dean of I&C. He is a recipient of a Fulbright Scholarship. He is a co-author of the book Modern Coding Theory, published by Cambridge University Press, a co-recipient of the 2002 and the 2013 IEEE Information Theory Society Paper Award, and recipient of the 2011 IEEE Koji Kobayashi Award, as well as the 2014 IEEE Hamming Medal.