2012/09/21 by Michael Molloy, Molloy, Michael, Ricardo Restrepo +1
Computer Science · Mathematics · #Combinatorics (math.CO) #Constraint Satisfaction and Optimization #Data Management and Algorithms #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Rough Sets and Fuzzy Logic #cs.DM #math.CO
paper · pdf · doi:10.48550/arxiv.1209.4829
arxiv created 2012/09/21 · openalex publication_date 2012/09/21 · arxiv updated 2012/09/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We determine the exact freezing threshold, rf, for a family of models of random boolean constraint satisfaction problems, including NAE-SAT and hypergraph 2-colouring, when the constraint size is sufficiently large. If the constraint-density of a random CSP, F, in our family is greater than rf then for almost every solution of F, a linear number of variables are frozen, meaning that their colours cannot be changed by a sequence of alterations in which we change o(n) variables at a time, always switching to another solution. If the constraint-density is less than rf, then almost every solution has o(n) frozen variables. Freezing is a key part of the clustering phenomenon that is hypothesized by non-rigorous techniques from statistical physics. The understanding of clustering has led to the development of advanced heuristics such as Survey Propogation. It has been suggested that the freezing threshold is a precise algorithmic barrier: that for densities below rf the random CSPs can be solved using very simple algorithms, while for densities above rf one requires more sophisticated techniques in order to deal with frozen clusters.