## Abstract

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 language | English (US) |
---|---|

Title of host publication | Spin Glass Theory and Far Beyond |

Subtitle of host publication | Replica Symmetry Breaking after 40 Years |

Publisher | World Scientific Publishing Co. |

Pages | 679-695 |

Number of pages | 17 |

ISBN (Electronic) | 9789811273926 |

ISBN (Print) | 9789811273919 |

DOIs | |

State | Published - Jan 1 2023 |

## All Science Journal Classification (ASJC) codes

- Engineering(all)
- Physics and Astronomy(all)