  Many problems in high-dimensional statistics appear to have a
statistical-computational gap: a range of values of the signal-to-noise ratio
where inference is information-theoretically possible, but (conjecturally)
computationally intractable. A canonical such problem is Tensor PCA, where we
observe a tensor $Y$ consisting of a rank-one signal plus Gaussian noise.
Multiple lines of work suggest that Tensor PCA becomes computationally hard at
a critical value of the signal's magnitude. In particular, below this
transition, no low-degree polynomial algorithm can detect the signal with high
probability; conversely, various spectral algorithms are known to succeed above
this transition. We unify and extend this work by considering tensor networks,
orthogonally invariant polynomials where multiple copies of $Y$ are
"contracted" to produce scalars, vectors, matrices, or other tensors. We define
a new set of objects, tensor cumulants, which provide an explicit,
near-orthogonal basis for invariant polynomials of a given degree. This basis
lets us unify and strengthen previous results on low-degree hardness, giving a
combinatorial explanation of the hardness transition and of a continuum of
subexponential-time algorithms that work below it, and proving tight lower
bounds against low-degree polynomials for recovering rather than just detecting
the signal. It also lets us analyze a new problem of distinguishing between
different tensor ensembles, such as Wigner and Wishart tensors, establishing a
sharp computational threshold and giving evidence of a new
statistical-computational gap in the Central Limit Theorem for random tensors.
Finally, we believe these cumulants are valuable mathematical objects in their
own right: they generalize the free cumulants of free probability theory from
matrices to tensors, and share many of their properties, including additivity
under additive free convolution.
