Hiding Quiet Solutions in Random Constraint Satisfaction Problems

Florent Krzakala, Lenka Zdeborová

We study constraint satisfaction problems on the so-called 'planted' random ensemble. We show that for a certain class of problems, e.g. graph coloring, many of the properties of t…