TY - EJOUR
DO - 10.1007/s10955-012-0664-x
AB - We consider chains of random constraint satisfaction models that are spatially coupled across a finite window along the chain direction. We investigate their phase diagram at zero temperature using the survey propagation formalism and the interpolation method. We prove that the SAT-UNSAT phase transition threshold of an infinite chain is identical to the one of the individual standard model, and is therefore not affected by spatial coupling. We compute the survey propagation complexity using population dynamics as well as large degree approximations, and determine the survey propagation threshold. We find that a clustering phase survives coupling. However, as one increases the range of the coupling window, the survey propagation threshold increases and saturates towards the phase transition threshold. We also briefly discuss other aspects of the problem. Namely, the condensation threshold is not affected by coupling, but the dynamic threshold displays saturation towards the condensation one. All these features may provide a new avenue for obtaining better provable algorithmic lower bounds on phase transition thresholds of the individual standard model.
T1 - Threshold Saturation in Spatially Coupled Constraint Satisfaction Problems
IS - 5
DA - 2013
AU - Hassani, S. Hamed
AU - Macris, Nicolas
AU - Urbanke, Ruediger
JF - JOURNAL OF STATISTICAL PHYSICS
SP - 807-850
VL - 150
EP - 807-850
PB - Springer Verlag
PP - New York
ID - 185300
KW - Random constraint satisfaction
KW - Survey propagation
KW - Spin glass
KW - Spatial coupling
KW - Interpolation method
UR - http://infoscience.epfl.ch/record/185300/files/constraintsatisfaction2013.pdf
ER -