New Bounds for Random Constraint Satisfaction Problems via Spatial Coupling

Abstract. This paper 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 where it has resulted 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 begin by describing how spatially coupled CSPs are constructed. We then use the results of a previous work to 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. As a result, these features provide a new avenue for obtaining better, provable, algorithmic lower bounds on satisfiability thresholds of the standard (uncoupled) CSP models. We then consider simple algorithms for solving coupled CSPs and provide the necessary machinery to analyze such algorithms. As a consequence, we derive new lower bounds for the satisfiability threshold of standard random CSPs. As we will see, some of these lower bounds surpass the current best lower bounds in the literature. Key words: algorithms, random structures, constraint satisfaction problems, spatial coupling, threshold saturation, phase transitions