  We develop new tools in the theory of nonlinear random matrices and apply
them to study the performance of the Sum of Squares (SoS) hierarchy on
average-case problems.
  The SoS hierarchy is a powerful optimization technique that has achieved
tremendous success for various problems in combinatorial optimization, robust
statistics and machine learning. It's a family of convex relaxations that lets
us smoothly trade off running time for approximation guarantees. In recent
works, it's been shown to be extremely useful for recovering structure in high
dimensional noisy data. It also remains our best approach towards refuting the
notorious Unique Games Conjecture.
  In this work, we analyze the performance of the SoS hierarchy on fundamental
problems stemming from statistics, theoretical computer science and statistical
physics. In particular, we show subexponential-time SoS lower bounds for the
problems of the Sherrington-Kirkpatrick Hamiltonian, Planted Slightly Denser
Subgraph, Tensor Principal Components Analysis and Sparse Principal Components
Analysis. These SoS lower bounds involve analyzing large random matrices,
wherein lie our main contributions. These results offer strong evidence for the
truth of and insight into the low-degree likelihood ratio hypothesis, an
important conjecture that predicts the power of bounded-time algorithms for
hypothesis testing.
  We also develop general-purpose tools for analyzing the behavior of random
matrices which are functions of independent random variables. Towards this, we
build on and generalize the matrix variant of the Efron-Stein inequalities. In
particular, our general theorem on matrix concentration recovers various
results that have appeared in the literature. We expect these random matrix
theory ideas to have other significant applications.
