Constraint optimization and landscapes
arXiv:0709.1023 · doi:10.1140/epjb/e2008-00052-x
Abstract
We describe an effective landscape introduced in [1] for the analysis of Constraint Satisfaction problems, such as Sphere Packing, K-SAT and Graph Coloring. This geometric construction reexpresses these problems in the more familiar terms of optimization in rugged energy landscapes. In particular, it allows one to understand the puzzling fact that unsophisticated programs are successful well beyond what was considered to be the `hard' transition, and suggests an algorithm defining a new, higher, easy-hard frontier.
Contribution to STATPHYS23
References in corpus (9)
- Jamming at Zero Temperature and Zero Applied Stress: the Epitome of Disorder
- Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
- The random K-satisfiability problem: from an analytic solution to an efficient algorithm
- On the Rigidity of Amorphous Solids
- Rigorous Inequalities between Length and Time Scales in Glassy Systems
- Coloring random graphs
- A Landscape Analysis of Constraint Satisfaction Problems
- Learning by message-passing in networks of discrete synapses
- Instability of one-step replica-symmetry-broken phase in satisfiability problems