  We determine the exact freezing threshold, r^f, 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 r^f 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 r^f, 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 r^f the random CSPs can be solved
using very simple algorithms, while for densities above r^f one requires more
sophisticated techniques in order to deal with frozen clusters.
