Average-Case Computational Complexity of Tensor Decomposition

Suppose we are given a random rank-r order-3 tensor---that is, an n-by-n-by-n array of numbers that is the sum of r random rank-1 terms---and our goal is to recover the individual rank-1 terms. In principle this decomposition task is possible when r<cn2 for a constant c, but all known poly-time algorithms require r<<n3/2. Is this a fundamental barrier for efficient algorithms?

In recent years, the average-case complexity of various high-dimensional statistical tasks has been resolved in restricted-but-powerful models of computation such as statistical queries, sum-of-squares, or low-degree polynomials. However, the hardness of tensor decomposition has remained elusive, and I will explain what makes this problem difficult. We show the first formal hardness for average-case tensor decomposition: when r>>n3/2, the decomposition task is hard for algorithms that can be expressed as low-degree polynomials in the tensor entries.