Lower Bounds on Thresholds of Graphical Models from Spatial Coupling: Applications to Coding and Constraint Satisfaction
Tuesday, May 19, 2015 - 9:00am - 9:50am
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.