Average-Case Reductions for $k$-XOR and Tensor PCA

Abstract

We study the computational properties of two canonical planted average-case problems -- noisy planted $k$-XOR and Tensor PCA -- by formally unifying them into a family of planted problems parametrized by tensor order $k$, number of entries $m$, and noise level $\hat{I}´$. We build a wide range of poly-time average-case reductions within this family, across all regimes $m\in [1,n^k]$. In the denser $m\ge n^{k/2}$ regime, our reductions preserve proximity to the computational threshold, and, as a central application, reduce conjectured-hard $k$-XOR instances with $m\approx n^{k/2}$ to conjectured-hard instances of Tensor PCA. Additionally, we give new order-reducing maps at fixed densities (e.g., $5\to 4$ for $k$-XOR with $m\approx n^{k/2}$ entries and $7\to 4$ for Tensor PCA). In the sparser $m\le n^{k/2}$ regime, we relate instances of different orders, reducing, for example, $7$-XOR with $m=n^{3.4}$ to the classical setting of $3$-XOR with $m=\tilde{\hat{I}}˜(n^{1.4})$. Taken together, these results establish a hardness partial order in the space of planted tensor models.

112 pages, 6 figures