We consider the spherical perceptron with Gaussian disorder. This is the set $S$ of points $\mathbf{\sigma} \in R^N$ on the sphere of radius $\sqrt{N}$ satisfying $\langle \mathbf{g}_a , \mathbf{\sigma} \rangle \ge k\sqrt{N}\,$ for all $1 \le a \le M$, where $(\mathbf{g}_a)_{a=1}^M$ are independent standard gaussian vectors and $k \in R$ is fixed. In other words it is an intersection of random half-spaces which do not contain the origin when $k>0$ and which do contain the origin when $k\leq 0$. Various characteristics of $S$, such as its surface measure and the largest $M$ for which it is non-empty, were computed heuristically in statistical physics in the asymptotic regime $N \to \infty$, $M/N \to \alpha$. Rigorous results for these questions have been achieved when $k\geq 0$. In this regime, the problem has an ``as simple as possible" replica symmetric structure. Moreover from an algorithmic point of view, the problem of computing a point in $S$ reduces to a convex optimization problem. By contrast, in the case $k<0$, $S$ is conjectured to exhibit a hierarchical tree-like geometry known as full replica-symmetry breaking (FRSB) close to the satisfiability threshold $\alpha_{{\rm\tiny SAT}}(k)$, with characteristics captured by a Parisi variational principle akin to the one appearing in the Sherrington-Kirkpatrick model.

In this work we exhibit an efficient algorithm which, given oracle access to the solution of the Parisi variational principle, exploits this conjectured FRSB structure for $k<0$ and outputs a vector $\hat{\mathbf{\sigma}}$ satisfying $\langle \mathbf{g}_a , \hat{\mathbf{\sigma}}\rangle \ge k \sqrt{N}$ for all $1\le a \le M$ and lying on a sphere of non-trivial radius $\sqrt{\bar{q} N}$, where $\bar{q} \in (0,1)$ is the right-end of the support of the associated Parisi measure. We expect $\hat{\mathbf{\sigma}}$ to be approximately the barycenter of a pure state of the spherical perceptron. Moreover we expect that $\bar{q} \to 1$ as $\alpha \to \alpha_{{\rm\tiny SAT}}(k)$, so that $\big\langle \mathbf{g}_a,\frac{\hat{\mathbf{\sigma}}}{|\hat{\mathbf{\sigma}}|}\big\rangle \geq (k-o(1))\sqrt{N}$ near criticality. This is joint work with Ahmed El Alaoui.