Cristopher Moore Santa Fe Institute

Defn.Let $x \in{+1,-1}^n$ be uniformly random, and let $Y$ be a noisy version of the rank-one tensor consisting of the $p$th tensor power of $x$, namely $Y = \lambda x^{\otimes p} + W$. Here $W$ is a noise tensor whose entries are independent Gaussians with mean $0$ and variance $1$ except that $W$ is symmetric, and $\lambda$ is a signal-to-noise ratio. (The asymmetric version where $Y = \lambda x_1 \otimes x_2 \otimes \cdots \otimes x_p + W$ is equally interesting.)

Problem.If $\lambda \gg n^{(1-p)/2}$ it is information-theoretically possible to approximately recover $x$ from $Y$, i.e., to find a vector $\hat{x}$ that agrees with $x$ at a fraction of coordinates bounded above $1/2$. We know of polynomial-time algorithms that do this whenever $\lambda \gg n^{p/4}$. These two thresholds coincide when $p=2$, where $Y$ is a random matrix with a rank-one perturbation, but when $p \ge 3$ there is a gap between them. We believe that between these two thresholds, approximate recovery is possible but takes exponential time. Can you find any evidence for or against this conjecture?

## Additional Questions?

If you have additional questions, feel free to reach out to a maintainer / contributor on the contact page.