450 citations · 5.9k across the 79 of their papers we have counts for
Showing 2008Show all
3 papers · 1 filter
cond-mat.dis-nn2008★ 57 cited
Constraint satisfaction problems with isolated solutions are hard
Lenka Zdeborová, Marc Mézard
We study the phase diagram and the algorithmic hardness of the random `locked' constraint satisfaction problems, and compare them to the commonly studied 'non-locked' problems like…
q-bio.NC2008
Constraint satisfaction problems and neural networks: a statistical physics perspective
Marc Mezard, Thierry Mora
A new field of research is rapidly expanding at the crossroad between statistical physics, information theory and combinatorial optimization. In particular, the use of cutting edge…
cond-mat.stat-mech2008★ 58 cited
Locked constraint satisfaction problems
Lenka Zdeborová, Marc Mézard
We introduce and study the random "locked" constraint satisfaction problems. When increasing the density of constraints, they display a broad "clustered" phase in which the space o…