Hiding Quiet Solutions in Random Constraint Satisfaction Problems

TL;DR

Planting guarantees satisfiability, but can alter an ensemble, and when planted instances remain difficult is less understood than for purely random CSPs. The paper analyzes quiet planting through q-coloring, finding planted/random ensemble equivalence below c_c and a hard/easy boundary at c_l=(q−1)^2.

• Problem

  Planting guarantees satisfiability, but it changes ensemble properties, and when planted instances remain difficult is less understood than for purely random CSPs.

  Source: p. 1

• Method

  The paper studies a natural quiet-planting scheme for q-coloring and uses the cavity method to analyze its solution structure and phase diagram.

  Source: p. 1

• Results

  For q-coloring, planted and purely random ensembles are asymptotically equivalent for c < c_c, and the hard/easy transition coincides with liquid instability at c_l=(q−1)^2.

  Source: pp. 3–4

• Takeaways & Limitations

  Quiet planting can generate planted instances without influencing most ensemble characteristics in CSPs whose purely random BP fixed point is uniform.

  Source: pp. 1, 4

  The results apply to CSPs with a uniform BP fixed point in the purely random ensemble; random satisfiability, whose fixed point is nonuniform, is not covered.

  Source: p. 4