We consider the spherical perceptron problem: this is the problem of finding a point on the sphere subject to a number of random linear inequalities. This problem and its variants appear in combinatorics, in machine learning as models for one-layer neural networks, and as analytically tractable models for the study of critical properties of jamming of hard spheres. The structure of solutions has been studied in statistical physics, but still poorly understood from the rigorous mathematical point of view.

In this talk I will review the relevant literature and will discuss an algorithmic approach attempting to compute a valid solution up to the satisfiability threshold predicted by statistical physics. This result is conditional on the validity of a conjecture concerning structure of the set of solutions, known as ‘full replica-symmetry breaking’. I will discuss a possible extension to the binary perceptron, where the desired solution must have binary coordinates. This is joint work with Mark Sellke.