In this review article we discuss connections between the physics of disordered systems,
phase transitions in inference problems, and computational hardness. We introduce two …

We prove, under an assumption on the critical points of a real-valued function, that the
symmetric Ising perceptron exhibits thefrozen 1-RSB'structure conjectured by Krauth and …

We consider the Ising perceptron model with N spins and M= N* alpha patterns, with a
general activation function U that is bounded above. For U bounded away from zero, or U a …

It was recently shown that almost all solutions in the symmetric binary perceptron are
isolated, even at low constraint densities, suggesting that finding typical solutions is hard. In …

The binary (or Ising) perceptron is a toy model of a single-layer neural network and can be
viewed as a random constraint satisfaction problem with a high degree of connectivity. The …

We consider the symmetric binary perceptron model, a simple model of neural networks that
has gathered significant attention in the statistical physics, information theory and probability …

We study a family of Ising perceptron models with {0, 1}-valued activation functions. This
includes the classical half-space models, as well as some of the symmetric models …

For many computational problems involving randomness, intricate geometric features of the
solution space have been used to rigorously rule out powerful classes of algorithms. This is …

In the negative perceptron problem we are given n data points (xi, yi), where xi is ad-
dimensional vector and yi∈{+ 1,-1} is a binary label. The data are not linearly separable and …

We consider the spherical perceptron with Gaussian disorder. This is the set S of points σ∈
RN on the sphere of radius N satisfying⟨ ga, σ⟩≥ κ N for all 1≤ a≤ M, where (ga) a= 1 M …