Figure 2

Fraction of variables frozen in their planted colors in 5-coloring of a $N={10}^5$ graph. Data obtained from the BP fixed point when initialized randomly (full triangles) and in the planted configuration (also called the whitening [20], empty circles), compared to the theoretical predictions [10, 13] (full and dashed lines). For $c>c_l=16$ BP converges spontaneously to the planted fixed point. For $c<14.04$ [13] there are no frozen variables in the planted cluster. Inset: Fraction of monochromatic edges versus the number of sweeps of the Walk-COL algorithm [10] in 5-coloring of a purely random and a planted graph, $N={10}^5$. Quiet planting does not seem to affect the computational hardness in the region $c<c_s$.Reuse & Permissions

Figure 3

Finite temperature phase diagram of the planted 5-coloring. At high temperature the liquid is the unique Gibbs state. Below the higher spinodal line $T_1$ a planted (solid) Gibbs state appears, and becomes thermodynamically dominant at the liquid-solid transition. The supercooled liquid state is locally stable until the lower spinodal line $T_2$. The liquid undergoes the usual dynamical and Kauzmann (ideal) glass transitions (data from 10). The thick line depicts the algorithmically hard region, the left boundary being the freezing transition [10]. Inset: Energy versus temperature in Monte Carlo annealing with rate $\delta T={10}^{-2}$, ${10}^{-3}$, ${10}^{-4}$, and ${10}^{-5}$ per sweep for $N=5\times {10}^5$ at $c=20>c_l$. Above $c_l$ a slow enough annealing undergoes a transition towards the planted state.Reuse & Permissions