Computer Science – Computational Complexity
Scientific paper
2011-12-23
Computer Science
Computational Complexity
Scientific paper
We consider chains of random Constraint Satisfaction Problems that are spatially coupled across a finite window along the chain direction. We investigate their phase diagram using the level-1 zero-temperature cavity and interpolation methods. We prove that the 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 complexity using population dynamics and also large degree approximations, and determine the survey propagation threshold, which marks the onset of clustering of solutions. 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 briefly explain why these features may provide a new avenue for obtaining algorithmic lower bounds on phase transition thresholds. The saturation of the survey propagation threshold observed here, is very similar to the saturation of the belief propagation threshold towards the optimal one, that has been observed in terminated convolutional (or spatially coupled) Low-Density Parity-Check codes.
Hassani Steven H.
Macris Nicolas
Urbanke Rudiger
No associations
LandOfFree
Threshold Saturation in Spatially Coupled Constraint Satisfaction Problems does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Threshold Saturation in Spatially Coupled Constraint Satisfaction Problems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Threshold Saturation in Spatially Coupled Constraint Satisfaction Problems will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-193202