Threshold saturation in spatially coupled constraint satisfaction problems
From MaRDI portal
Publication:1949335
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.
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
Cites work
- scientific article; zbMATH DE number 437557 (Why is no real title available?)
- scientific article; zbMATH DE number 4102824 (Why is no real title available?)
- scientific article; zbMATH DE number 1273988 (Why is no real title available?)
- scientific article; zbMATH DE number 1303577 (Why is no real title available?)
- scientific article; zbMATH DE number 1332581 (Why is no real title available?)
- scientific article; zbMATH DE number 1121929 (Why is no real title available?)
- A Simple Proof of Maxwell Saturation for Coupled Scalar Recursions
- Coloring random graphs
- Gibbs measures and phase transitions
- Gibbs states and the set of solutions of random constraint satisfaction problems
- Information, Physics, and Computation
- On belief propagation guided decimation for random \(k\)-SAT
- On the concentration of the number of solutions of random satisfiability formulas
- Replica bounds for optimization problems and diluted spin systems
- Rounding effects of quenched randomness on first-order phase transitions
- Spin glasses: a new direction for probability theory?
- Sudden emergence of a giant \(k\)-core in a random graph
- The cavity method at zero temperature
- The high temperature region of the Viana-Bray diluted spin glass model
- The thermodynamic limit in mean field spin glass models
- Threshold Saturation for Spatially Coupled LDPC and LDGM Codes on BMS Channels
- Threshold Saturation via Spatial Coupling: Why Convolutional LDPC Ensembles Perform So Well over the BEC
- Threshold saturation in spatially coupled constraint satisfaction problems
- Threshold values of random K‐SAT from the cavity method
- Time-varying periodic convolutional codes with low-density parity-check matrix
- Two solutions to diluted \(p\)-spin models and XORSAT problems
- Wave-Like Solutions of General 1-D Spatially Coupled Systems
Cited in
(4)
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)
