Rigorous Results: Random Constraint Satisfaction Problems

This chapter surveys some of the rigorous mathematical results in the theory of random constraint satisfaction problems (random CSPs). The first part covers the replica symmetric regime, where the so-called “planting trick” has been leveraged to gain understanding of the behavior of typical solutions. Moreover, the onset of replica symmetry breaking has been shown to coincide with information-theoretic thresholds in many interesting models. The second part of the survey covers the regime of (one-step) replica symmetry breaking, where combinatorial models of solution clusters have been analyzed to produce sharp asymptotic results such as satisfiability thresholds.