58 citations · 184 across the 6 of their papers we have counts for
Showing cs.CCShow all
2 papers · 1 filter
cs.CC2007★ 11 cited
Phase Transitions and Computational Difficulty in Random Constraint Satisfaction Problems
Florent Krzakala, Lenka Zdeborová
We review the understanding of the random constraint satisfaction problems, focusing on the q-coloring of large random graphs, that has been achieved using the cavity method of the…
cs.CC2007★ 39 cited
Random subcubes as a toy model for constraint satisfaction problems
Thierry Mora, Lenka Zdeborova
We present an exactly solvable random-subcube model inspired by the structure of hard constraint satisfaction and optimization problems. Our model reproduces the structure of the s…