  We consider the spherical perceptron with Gaussian disorder. This is the set
$S$ of points $\sigma \in \mathbb{R}^N$ on the sphere of radius $\sqrt{N}$
satisfying $\langle g_a , \sigma \rangle \ge \kappa\sqrt{N}\,$ for all $1 \le a
\le M$, where $(g_a)_{a=1}^M$ are independent standard gaussian vectors and
$\kappa \in \mathbb{R}$ is fixed. 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$. The case $\kappa<0$ is of special interest as $S$ is
conjectured to exhibit a hierarchical tree-like geometry known as "full
replica-symmetry breaking" (FRSB) close to the satisfiability threshold
$\alpha_{\text{SAT}}(\kappa)$, and whose characteristics are captured by a
Parisi variational principle akin to the one appearing in the
Sherrington-Kirkpatrick model. In this paper we design an efficient algorithm
which, given oracle access to the solution of the Parisi variational principle,
exploits this conjectured FRSB structure for $\kappa<0$ and outputs a vector
$\hat{\sigma}$ satisfying $\langle g_a , \hat{\sigma}\rangle \ge \kappa
\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{\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_{\text{SAT}}(\kappa)$, so that
$\big\langle g_a,\hat{\sigma}/|\hat{\sigma}|\big\rangle \geq
(\kappa-o(1))\sqrt{N}$ near criticality.
