Hardness of Sampling in Random Constraint Satisfaction Problems

Abstract

Random constraint satisfaction problems undergo a sequence of geometric phase transitions well before satisfiability is lost, and these transitions are believed to underlie the failure of efficient algorithms. This thesis studies that connection for the stronger task of sampling satisfying assignments uniformly at random. The first main result is a general criterion showing that variable rigidity forces \emph{transport disorder chaos} for the uniform measure on solutions. Here, rigidity means that the value of a typical variable cannot be changed without changing many others as well, while transport disorder chaos means that a microscopic perturbation of the instance causes a macroscopic change in the solution distribution. Combined with the framework of El Alaoui, Montanari, and Sellke, this yields a barrier to \emph{stable sampling}: no randomized algorithm can simultaneously sample accurately from the solution distribution and remain stable under small perturbations of the input. The second main result establishes this criterion for random $k$-NAE-SAT. The key ingredient is a transfer theorem between the planted and uniform models, proved using log-concentration of the number of solutions together with a sharp-threshold argument. This transfer theorem allows geometric information proved in the planted model to be carried over to the uniform model, where it yields shattering and linear-variable rigidity in the relevant density regime. Combining these ingredients gives a rigorous failure-of-stable-sampling result for random $k$-NAE-SAT. The same general criterion also gives analogous consequences for other sparse random CSPs, including random $k$-SAT and random graph $k$-coloring via existing rigidity results.