  We devise a parameterized family of distributions, the high-entropy step
distributions (HES), which are expressive enough to capture near-optima of
spherical spin glass models in the full Replica Symmetry Breaking (fRSB) regime
and yet permit low-degree Sum-of-Squares (SoS) certificates that no such
distribution can achieve value slightly larger than the true optimum. This
yields a SoS optimization program and rounding scheme that attains near-optimal
solutions for spherical spin glasses in the fRSB regime. In other regimes, the
same results occur at the ALG value, which is a conjectured best-value
attainable by any polynomial time algorithm. These SoS programs optimize over
families of distributions of possible solutions, and circumvent the oft-cited
impossibility of providing a low-degree SoS proof of concentration of measure
by instead proving the same bounds only in expectation on solution
distributions that can be produced by the chosen rounding algorithm. The new
SoS hierarchy does not make any specific reference to the spherical spin glass
problem, and we conjecture that it can be applied to a broad range of
average-case problems to obtain value that is optimal among polynomial-time
algorithms. We give evidence for this with examples of ensembles that provably
fool certain local iterative algorithms but for which there is either proof or
evidence that the SoS program is better. This opens the door to addressing a
question posed by Barak about the possible optimality of SoS on average-case
optimization problems, and by Schramm about reductions between different
families of algorithms for average-case problems. In this paper, we give
low-degree SoS proofs certifying key properties about HES distributions as well
as the ALG threshold for spherical spin glasses. The rounding algorithm is
introduced and analyzed in a companion paper.
