The simplest model of jamming
Silvio Franz, Giorgio Parisi · Journal of Physics A Mathematical and Theoretical · 2016
We study a well known neural network model—the perceptron—as a simple statistical physics model of jamming of hard objects. We exhibit two regimes: (1) a convex optimization regime where jamming is hypostatic and non-critical; (2) a non-convex optimization regime where jamming is isostatic and critical. We characterize the critical jamming phase through exponents describing the distribution laws of forces and gaps. Surprisingly we find that these exponents coincide with the corresponding ones recently computed in high dimensional hard spheres. In addition, modifying the perceptron to a random linear programming problem, we show that isostaticity is not a sufficient condition for singular force and gap distributions. For that, fragmentation of the space of solutions (replica symmetry breaking) appears to be a crucial ingredient. We hypothesize universality for a large class of non-convex constrained satisfaction problems with continuous variables.