  The Sum-of-Squares (SoS) hierarchy of semidefinite programs is a powerful
algorithmic paradigm which captures state-of-the-art algorithmic guarantees for
a wide array of problems. In the average case setting, SoS lower bounds provide
strong evidence of algorithmic hardness or information-computation gaps. Prior
to this work, SoS lower bounds have been obtained for problems in the "dense"
input regime, where the input is a collection of independent Rademacher or
Gaussian random variables, while the sparse regime has remained out of reach.
We make the first progress in this direction by obtaining strong SoS lower
bounds for the problem of Independent Set on sparse random graphs. We prove
that with high probability over an Erdos-Renyi random graph $G\sim
G_{n,\frac{d}{n}}$ with average degree $d>\log^2 n$, degree-$D_{SoS}$ SoS fails
to refute the existence of an independent set of size $k =
\Omega\left(\frac{n}{\sqrt{d}(\log n)(D_{SoS})^{c_0}} \right)$ in $G$ (where
$c_0$ is an absolute constant), whereas the true size of the largest
independent set in $G$ is $O\left(\frac{n\log d}{d}\right)$.
  Our proof involves several significant extensions of the techniques used for
proving SoS lower bounds in the dense setting. Previous lower bounds are based
on the pseudo-calibration heuristic of Barak et al [FOCS 2016] which produces a
candidate SoS solution using a planted distribution indistinguishable from the
input distribution via low-degree tests. In the sparse case the natural planted
distribution does admit low-degree distinguishers, and we show how to adapt the
pseudo-calibration heuristic to overcome this.
  Another notorious technical challenge for the sparse regime is the quest for
matrix norm bounds. In this paper, we obtain new norm bounds for graph matrices
in the sparse setting.
