UC Berkeley

Constraints satisfaction problem (CSP) is a family of computation problems that are generally hard to solve in the worst case, which motivates the study of average cases by looking at random CSPs. This thesis studies problems related to random constraints satisfaction problems, in particular its different phase transitions in the large system limit as the level of constraints increases.

The first part of this thesis studies the number of solutions in a typical problem instance. It has long been observed that shortly before the satisfiability phase transition where solutions stop to exist, the number of solutions in a typical instance no longer concentrate around its expectation. Guided by the 1-step replica symmetry breaking heuristics in statistical physics, we prove the correct formula for the typical number of the solutions up to the exponent.

The second part focus on the clustering threshold around which algorithms have been observed to slow down. Different opinions exist for the reason of this algorithmic barrier. One is the shattering of solution space which is conjectured to happen at the clustering threshold. The other is the onset of frozen variables happening at a nearby rigidity threshold. Previous analysis on the clustering threshold was not strong enough to differentiate the two phase transitions. Using a detailed analysis of certain distributional recursion, we show that the reconstruction threshold on trees, which is conjectured to coincide with the clustering threshold, is strictly smaller than the rigidity threshold, laying ground for further studies.

The last part of the thesis studied the Glauber dynamics of graph colorings on $d$-regular trees. By comparing the Glauber dynamics to a variant of block dynamics, we show that the mixing time, and hence the speed of the related MCMC algorithm, undergoes a phase transition at the reconstruction threshold.