Figure 2

(Color online) (a) probability that there exists an unfrozen solution as a function of the constraint density $\alpha$ for different system sizes. The clustering [10] and satisfiability [9] transitions are marked for comparison. (a) A 1:20 zoom-in on the critical (crossing) point. Our estimate for the freezing transition is ${\alpha }_f=4.254\pm 0.009$. The curves are cubic fits in the interval (4,4.4). The arrows represent estimates of the limits of performance of the best known stochastic local search [26, 33] and survey propagation [34, 35] algorithms.Reuse & Permissions