Rigorous Results: Random Constraint Satisfaction Problems

Amin Coja-Oghlan, Allan Sly, Nike Sun

Research output: Chapter in Book/Report/Conference proceedingChapter


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.

Original languageEnglish (US)
Title of host publicationSpin Glass Theory and Far Beyond
Subtitle of host publicationReplica Symmetry Breaking after 40 Years
PublisherWorld Scientific Publishing Co.
Number of pages17
ISBN (Electronic)9789811273926
ISBN (Print)9789811273919
StatePublished - Jan 1 2023

All Science Journal Classification (ASJC) codes

  • General Engineering
  • General Physics and Astronomy


Dive into the research topics of 'Rigorous Results: Random Constraint Satisfaction Problems'. Together they form a unique fingerprint.

Cite this