000185300 001__ 185300
000185300 005__ 20190316235618.0
000185300 0247_ $$2doi$$a10.1007/s10955-012-0664-x
000185300 02470 $$2ISI$$a000315510200001
000185300 037__ $$aARTICLE
000185300 245__ $$aThreshold Saturation in Spatially Coupled Constraint Satisfaction Problems
000185300 269__ $$a2013
000185300 260__ $$bSpringer Verlag$$c2013$$aNew York
000185300 300__ $$a44
000185300 336__ $$aJournal Articles
000185300 520__ $$aWe 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.
000185300 6531_ $$aRandom constraint satisfaction
000185300 6531_ $$aSurvey propagation
000185300 6531_ $$aSpin glass
000185300 6531_ $$aSpatial coupling
000185300 6531_ $$aInterpolation method
000185300 700__ $$0242512$$g177411$$aHassani, S. Hamed
000185300 700__ $$0241807$$g107423$$aMacris, Nicolas
000185300 700__ $$aUrbanke, Ruediger$$g124369$$0240188
000185300 773__ $$j150$$tJOURNAL OF STATISTICAL PHYSICS$$k5$$q807-850
000185300 8564_ $$uhttps://infoscience.epfl.ch/record/185300/files/constraintsatisfaction2013.pdf$$zn/a$$s1423373$$yn/a
000185300 909C0 $$xU10432$$0252058$$pLTHC
000185300 909CO $$ooai:infoscience.tind.io:185300$$qGLOBAL_SET$$pIC$$particle
000185300 917Z8 $$x124369
000185300 917Z8 $$x107423
000185300 917Z8 $$x107423
000185300 937__ $$aEPFL-ARTICLE-185300
000185300 973__ $$rREVIEWED$$sPUBLISHED$$aEPFL
000185300 980__ $$aARTICLE