Hassani, S. Hamed
Macris, Nicolas
Urbanke, Ruediger
Threshold Saturation in Spatially Coupled Constraint Satisfaction Problems
JOURNAL OF STATISTICAL PHYSICS
10.1007/s10955-012-0664-x
150
5
807-850
44
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.
Random constraint satisfaction;
Survey propagation;
Spin glass;
Spatial coupling;
Interpolation method;
Springer Verlag
New York
2013
http://infoscience.epfl.ch/record/185300/files/constraintsatisfaction2013.pdf;