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

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 $\delta$. 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\mathrm{/}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\mathrm{/}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\mathrm{/}2}$ entries and $7\to 4$ for Tensor PCA). In the sparser $m\le n^{k\mathrm{/}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{\mathrm{\Theta }}(n^{1.4})$. Taken together, these results establish a hardness partial order in the space of planted tensor models.