Lower Bounds on Thresholds of Graphical Models from Spatial Coupling: Applications to Coding and Constraint Satisfaction

Tuesday, May 19, 2015 - 9:00am - 9:50am
Keller 3-180
Nicolas Macris (École Polytechnique Fédérale de Lausanne (EPFL))
This talk will be about a novel technique called spatial coupling originally invented for constructing better error correcting codes. One can use spatial coupling as a mathematical tool to derive properties of standard graphical models via an analysis of a coupled version. A general methodology for obtaining provable better (sometimes optimal) lower bounds for thresholds in coding theory and random constraint satisfaction problems will be outlined.
MSC Code: