  We study the random binary symmetric perceptron problem, focusing on the
behavior of rare high-margin solutions. While most solutions are isolated, we
demonstrate that these rare solutions are part of clusters of extensive
entropy, heuristically corresponding to non-trivial fixed points of an
approximate message-passing algorithm. We enumerate these clusters via a local
entropy, defined as a Franz-Parisi potential, which we rigorously evaluate
using the first and second moment methods in the limit of a small constraint
density $\alpha$ (corresponding to vanishing margin $\kappa$) under a certain
assumption on the concentration of the entropy. This examination unveils
several intriguing phenomena: i) We demonstrate that these clusters have an
entropic barrier in the sense that the entropy as a function of the distance
from the reference high-margin solution is non-monotone when $\kappa \le 1.429
\sqrt{-\alpha/\log{\alpha}}$, while it is monotone otherwise, and that they
have an energetic barrier in the sense that there are no solutions at an
intermediate distance from the reference solution when $\kappa \le 1.239
\sqrt{-\alpha/ \log{\alpha}}$. The critical scaling of the margin $\kappa$ in
$\sqrt{-\alpha/\log\alpha}$ corresponds to the one obtained from the earlier
work of Gamarnik et al. (2022) for the overlap-gap property, a phenomenon known
to present a barrier to certain efficient algorithms. ii) We establish using
the replica method that the complexity (the logarithm of the number of clusters
of such solutions) versus entropy (the logarithm of the number of solutions in
the clusters) curves are partly non-concave and correspond to very large values
of the Parisi parameter, with the equilibrium being reached when the Parisi
parameter diverges.
