Ruediger Urbanke

Sharp thresholds in coding theory - when classical codes meet modern ideas

It is desirable for a family of codes to exhibiti a very sharp transition between the noise levels where the codes work well and the noise levels where they completely fail. The performance analysis of such codes therefore reduces to the following two problems: (i) showing that a sharp threshold exists, and (ii) determining where the threshold is located.

I will discuss techniques and notions that are useful for these two tasks. In particular, I will talks about code symmetry, EXIT functions and the area theorem, and threshold properties of monotone and symmetric boolean functions.

These ingredients will be applied to classical codes, such as Reed-Muller codes, as well as modern codes based on iterative decoding techniques, such as spatially-coupled codes. In particular, I will show how symmetry by itself implies that the family of codes has a sharp threshold and how EXIT functions and the area theorem can then often be used to locate the threshold and to show that it coincides with channel capacity.

Biography: Ruediger Urbanke (Phd, WashU, St. Louis, 1995) has been obsessed with questions in coding theory for the past 20 years. Fortunately his progress has been slow so that there are many problems left for him for the next 20 years. He likes sabbaticals, dreams about running marathons but is too lazy to practice for them, and owns more bicycles than can be rationally justified. Before joining EPFL in 1999, he enjoyed working at Bell Labs (Murray Hill) at the Mathematics of Communications Group.