Description:

Title: Phase transitions of random constraint satisfaction problems

Abstract: The framework of constraint satisfaction problems (CSPs) captures many fundamental problems in combinatorics and computer science, such as finding a proper coloring of a graph or solving Boolean satisfiability problems. To study the typical cases of CSPs, statistical physicists have proposed a detailed picture of the solution space for random CSPs based on non-rigorous methods from spin glass theory. In this talk, I will first survey the conjectured rich phase diagrams of random CSPs in the one-step replica symmetry breaking universality class. Then, I will describe mathematical progress in understanding the global and local geometry of solutions, particularly in random regular NAE-SAT problem. This is based on joint work with Danny Nam and Allan Sly.