A Landscape Analysis of Constraint Satisfaction Problems

By Florent Krzakala, Jorge Kurchan. 2007

123 citations recorded by the source corpus.

We discuss an analysis of constraint satisfaction problems, such as sphere packing, K-SAT, and graph coloring, in terms of an effective energy landscape. Several intriguing geometrical properties of the solution space become in this light familiar in terms of the well-studied ones of rugged (glassy) energy landscapes. A benchmark algorithm naturally suggested by this construction finds solutions in polynomial time up to a point beyond the clustering and in some cases even the thermodynamic transitions. This point has a simple geometric meaning and can be in principle determined with standard statistical mechanical methods, thus pushing the analytic bound up to which problems are guaranteed to be easy. We illustrate this for the graph 3- and 4-coloring problem. For packing problems the present discussion allows to better characterize the J-point, proposed as a systematic definition of random close packing, and to place it in the context of other theories of glasses.

Subfields: Computer Networks and Communications, Computer Vision and Pattern Recognition, Food Science, Algorithms & Complexity

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Networks and Communications

In Computer Vision and Pattern Recognition

In Food Science

In Algorithms & Complexity

Citations in the corpus

The jamming transition as a paradigm to understand the loss landscape of deep neural networks (2018, background): “[31] Florent Krzakala and Jorge Kurchan, “Landscape analysis of constraint satisfaction problems,” Physical Review E 76, 021122 (2007).”
Fractal free energy landscapes in structural glasses (2014, background): “It can be shown [5, 7, 8] that this structure corresponds to the standard 1-step replica symmetry breaking (1RSB) computation for models with quenched disorder, which is precisely the structure assumed in the original RFOT scenario [15, 16].”
A jamming transition from under- to over-parametrization affects loss landscape and generalization (2018, background): “In the last decade physicists have unveiled an analogy between the physical phenomenon of jamming [22], which characterizes the onset of rigidity in disordered packings of particles, and phase transitions taking place in certain classes of computational optimization and learning problems [26, 45, 15”
Edwards Statistical Mechanics for Jammed Granular Matter (2016, background): “Even more broadly, the jamming transition pertains to a larger family of computational problems named Constraint Satisfaction Problems (CSP) (Krzakala and Kurchan, 2007).”
Mean-field theory of hard sphere glasses and jamming (2008, background): “This point is very delicate and is receiving a lot of attention in the context of optimization problems (Krzakala and Kurchan, 2007), where it has not yet been solved.”
Triple descent and the two kinds of overfitting: where and why do they appear? (2020, background): “h point training error vanishes), then decreases monotonically again. This peak1 1Also called the jamming peak due to similarities with a well-studied phenomenon in the Statistical Physics literature [13, 14, 15, 16, 17]. Preprint. Under review. arXiv:2006.03509v1 [cs.LG] 5 Jun 2020 ’ 1 /LQHDU SHDN ”
Statistical physics of inference: thresholds and algorithms (2015, background): “the concept suggested but not analyzed in [131].”