Videos

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

Presenter
May 19, 2015
Keywords:
  • Coding theory
MSC:
  • 11H71
Abstract
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.