Phase Transitions of Random Constraint Satisfaction Problems

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 describe the rich phase diagrams of random CSPs that exhibit long-range correlations. Then, I will highlight the recent progress in characterizing both the global and local geometry of solutions, particularly in random regular NAE-SAT problem. Additionally, I will briefly discuss my other works in spin glass theory, community detection, high-dimensional classification, and their connections to random CSPs.

Share this Event