Marc Mezard, Matteo Palassini, Olivier Rivoire
Published 2005-07-19, updated 2005-11-02Version 2
We present a theoretical framework for characterizing the geometrical properties of the space of solutions in constraint satisfaction problems, together with practical algorithms for studying this structure on particular instances. We apply our method to the coloring problem, for which we obtain the total number of solutions and analyze in detail the distribution of distances between solutions.
Comments: 4 pages, 4 figures. Replaced with published version
Journal: Phys. Rev. Lett. 95, 200202 (2005)
Geometrical properties of Potts model during the coarsening regime
A residual-based message passing algorithm for constraint satisfaction problems
Threshold values, stability analysis and high-q asymptotics for the coloring problem on random graphs
