  In this paper, we construct general machinery for proving Sum-of-Squares
lower bounds on certification problems by generalizing the techniques used by
Barak et al. [FOCS 2016] to prove Sum-of-Squares lower bounds for planted
clique. Using this machinery, we prove degree $n^{\epsilon}$ Sum-of-Squares
lower bounds for tensor PCA, the Wishart model of sparse PCA, and a variant of
planted clique which we call planted slightly denser subgraph.
