Threshold saturation in spatially coupled constraint satisfaction problems
From MaRDI portal
Publication:1949335
DOI10.1007/S10955-012-0664-XzbMATH Open1266.82067arXiv1112.6320OpenAlexW2058957447MaRDI QIDQ1949335FDOQ1949335
S. Hamed Hassani, Nicolas Macris, Ruediger Urbanke
Publication date: 7 May 2013
Published in: Journal of Statistical Physics (Search for Journal in Brave)
Abstract: 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.
Full work available at URL: https://arxiv.org/abs/1112.6320
Recommendations
- Bounds for random constraint satisfaction problems via spatial coupling
- Catching the \(k\)-NAESAT threshold
- Survey propagation: An algorithm for satisfiability
- Gibbs states and the set of solutions of random constraint satisfaction problems
- Reconstruction and clustering in random constraint satisfaction problems
Phase transitions (general) in equilibrium statistical mechanics (82B26) Statistical mechanics of random media, disordered materials (including liquid crystals and spin glasses) (82D30)
Cites Work
- Title not available (Why is that?)
- Sudden emergence of a giant \(k\)-core in a random graph
- Rounding effects of quenched randomness on first-order phase transitions
- Title not available (Why is that?)
- Title not available (Why is that?)
- Gibbs measures and phase transitions
- The thermodynamic limit in mean field spin glass models
- Replica bounds for optimization problems and diluted spin systems
- Two solutions to diluted \(p\)-spin models and XORSAT problems
- Gibbs states and the set of solutions of random constraint satisfaction problems
- Coloring random graphs
- Combinatorial approach to the interpolation method and scaling limits in sparse random graphs
- Information, Physics, and Computation
- Title not available (Why is that?)
- On the concentration of the number of solutions of random satisfiability formulas
- Title not available (Why is that?)
- The high temperature region of the Viana-Bray diluted spin glass model
- Threshold values of random K‐SAT from the cavity method
- The cavity method at zero temperature
- Time-varying periodic convolutional codes with low-density parity-check matrix
- Title not available (Why is that?)
- Spin glasses: a new direction for probability theory?
- Threshold saturation in spatially coupled constraint satisfaction problems
- Wave-Like Solutions of General 1-D Spatially Coupled Systems
- Threshold Saturation for Spatially Coupled LDPC and LDGM Codes on BMS Channels
- A Simple Proof of Maxwell Saturation for Coupled Scalar Recursions
- Threshold Saturation via Spatial Coupling: Why Convolutional LDPC Ensembles Perform So Well over the BEC
- On belief propagation guided decimation for random k-SAT
Cited In (2)
This page was built for publication: Threshold saturation in spatially coupled constraint satisfaction problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1949335)
