indico    Complex systems and Biological physics seminar Next event Last event   | view:  |  manage export to personal scheduler  | 
user login 

 

New bounds on thresholds of constraint satisfaction problems from spatial coupling
  Complex systems and Biological physics seminar

Tuesday 28 January 2014
from 13:30 to 14:30
Speaker : Nicolas Macris (EPFL)
Abstract : This work is about a novel technique called spatial coupling and its application in the analysis of random constraint satisfaction problems (CSP). Spatial Coupling was recently invented in the area of error correcting codes thus resulting in efficient capacity achieving codes for a wide range of channels. However, this technique is not limited to problems in communications. It can be applied in the much broader context of graphical models. We describe here a general methodology for applying spatial coupling to constraint satisfaction problems. We argue that spatially coupled CSPs are much easier to solve than standard CSPs, while the satisfiability threshold of coupled and standard CSPs are the same. These features provide a new avenue for obtaining better, provable, algorithmic lower bounds on satisfiability thresholds of the standard CSP models. Some of these lower bounds surpass the current best (rigorous) lower bounds in the literature. (This is joint work with D. Achlioptas, H. Hassani and R. Urbanke)

Nordita  | Last modified 10 January 2014 18:18  |  HELP