The replica symmetric phase of random constraint satisfaction problems

Abstract

Random constraint satisfaction problems play an important role in computer science and combinatorics. For example, they provide challenging benchmark instances for algorithms and they have been harnessed in probabilistic constructions of combinatorial structures with peculiar features. In an important contribution [Krzakala et al., PNAS 2007] physicists made several predictions on the precise location and nature of phase transitions in random constraint satisfaction problems. Specifically, they predicted that their satisfiability thresholds are quite generally preceded by several other thresholds that have a substantial impact both combinatorially and computationally. These include the condensation phase transition, where long-range correlations between variables emerge, and the reconstruction threshold. In this paper we prove these physics predictions for a broad class of random constraint satisfaction problems. Additionally, we obtain contiguity results that have implications on Bayesian inference tasks, a subject that has received a great deal of interest recently (e.g., [Banks et al., COLT 2016]).

References in corpus (14)

• Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications
• Broken Replica Symmetry Bounds in the Mean Field Spin Glass Model
• Statistical physics of inference: Thresholds and algorithms
• Algorithmic barriers from phase transitions
• Hiding Quiet Solutions in Random Constraint Satisfaction Problems
• Information-theoretic thresholds from the cavity method
• Combinatorial approach to the interpolation method and scaling limits in sparse random graphs
• The asymptotic $k$-SAT threshold
• Catching the k-NAESAT Threshold
• The condensation transition in random hypergraph 2-coloring
• The condensation phase transition in random graph coloring
• Charting the replica symmetric phase
• Finite size corrections to disordered systems on Erdös-Rényi random graphs
• Planting colourings silently

Cited by in corpus (2)

• The random 2-SAT partition function
• Towards Geometry-Preserving Reductions Between Constraint Satisfaction Problems (and other problems in NP)