  We prove that for every $D \in \N$, and large enough constant $d \in \N$,
with high probability over the choice of $G \sim G(n,d/n)$, the \Erdos-\Renyi
random graph distribution, the canonical degree $2D$ Sum-of-Squares relaxation
fails to certify that the largest independent set in $G$ is of size
$o(\frac{n}{\sqrt{d} D^4})$. In particular, degree $D$ sum-of-squares
strengthening can reduce the integrality gap of the classical \Lovasz theta SDP
relaxation by at most a $O(D^4)$ factor.
  This is the first lower bound for $>4$-degree Sum-of-Squares (SoS) relaxation
for any problems on \emph{ultra sparse} random graphs (i.e. average degree of
an absolute constant). Such ultra-sparse graphs were a known barrier for
previous methods and explicitly identified as a major open direction
(e.g.,~\cite{deshpande2019threshold, kothari2021stressfree}). Indeed, the only
other example of an SoS lower bound on ultra-sparse random graphs was a
degree-4 lower bound for Max-Cut.
  Our main technical result is a new method to obtain spectral norm estimates
on graph matrices (a class of low-degree matrix-valued polynomials in
$G(n,d/n)$) that are accurate to within an absolute constant factor. All prior
works lose $\poly log n$ factors that trivialize any lower bound on $o(\log
n)$-degree random graphs. We combine these new bounds with several upgrades on
the machinery for analyzing lower-bound witnesses constructed by
pseudo-calibration so that our analysis does not lose any $\omega(1)$-factors
that would trivialize our results. In addition to other SoS lower bounds, we
believe that our methods for establishing spectral norm estimates on graph
matrices will be useful in the analyses of numerical algorithms on average-case
inputs.
