New bounds on thresholds of constraint satisfaction problems from spatial coupling
by
Nicolas Macris(EPFL)
→
Europe/Stockholm
Description
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)
