Spatial Coupling as a Proof Technique

Nov 5

Thursday, November 5, 2015

3:00 pm - 4:00 pm
Gross Hall 330


Ruediger Urbanke, EPFL

Graphical models and their associated greedy/message-passing algorithms make excellent error correcting codes as well as efficient compressive sensing systems and they are the natural setting for general random constraint satisfaction problems. Empirically, such systems, if properly chosen, work very well. Analytically, they are not always easy to handle. When we are interested in the behaviour of a function of a real variable it is sometimes useful to think of this function as defined on the whole complex plane. Even though the setting is now more general and seemingly more difficult, the analysis can simplify. E.g., think of a polynomial and its roots. For graphical models we can do something similar. Instead of thinking of one graphical model, we can imagine many of them coupled together spatially along a line. It turns out that for some problems not only is it easier to analyse a coupled system but understanding this coupled system also allows us to draw conclusion about the underlying uncoupled one. I will discuss this phenomenon in the framework of random constraint satisfaction problems. No prior familiarity with graphical models, spatial coupling or constraint satisfaction will be assumed. This talk is based on joint work with Dimitris Achlioptas, Hamed Hassani, and Nicolas Macris. refreshments