Universality of the SAT-UNSAT (jamming) threshold in non-convex continuous constraint satisfaction problems

By Silvio Franz, Giorgio Parisi, Maksim Sevelev, Pierfrancesco Urbani, Francesco Zamponi. 2017

100 citations recorded by the source corpus.

Random constraint satisfaction problems (CSP) have been studied extensively using statistical physics techniques. They provide a benchmark to study average case scenarios instead of the worst case one. The interplay between statistical physics of disordered systems and computer science has brought new light into the realm of computational complexity theory, by introducing the notion of clustering of solutions, related to replica symmetry breaking. However, the class of problems in which clustering has been studied often involve discrete degrees of freedom: standard random CSPs are random K-SAT (aka disordered Ising models) or random coloring problems (aka disordered Potts models). In this work we consider instead problems that involve continuous degrees of freedom. The simplest prototype of these problems is the perceptron. Here we discuss in detail the full phase diagram of the model. In the regions of parameter space where the problem is non-convex, leading to multiple disconnected clusters of solutions, the solution is critical at the SAT/UNSAT threshold and lies in the same universality class of the jamming transition of soft spheres. We show how the critical behavior at the satisfiability threshold emerges, and we compute the critical exponents associated to the approach to the transition from both the SAT and UNSAT phase. We conjecture that there is a large universality class of non-convex continuous CSPs whose SAT-UNSAT threshold is described by the same scaling solution.

Subfields: Computational Theory and Mathematics, Condensed Matter Physics, Statistics and Probability, Scaling & Learning Theory

How researchers see this paper

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

In Computational Theory and Mathematics

In Condensed Matter Physics

In Statistics and Probability

In Scaling & Learning Theory

Citations in the corpus

Scaling description of generalization with number of parameters in deep learning (2019, background): “We assume that this function is differentiable in its argument around zero, a fact know to be true for the perceptron [56, 57], thus N(̃m) = N ∗(0) + B0̃m + o(̃m).”
The jamming transition as a paradigm to understand the loss landscape of deep neural networks (2018, methodology): “Differently from the (nonconvex) perceptron, that was proven to lie in the same universality class as spherical particles [33, 34], we show that deep networks instead jam in a manner similar to ellipses.”
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”
Universality of jamming of nonspherical particles (2018, methodology): “(28), while for ∆ > 0 the Rμ play the same role of the particle sizes in the BP model.”