Average-Case Reductions for $k$-XOR and Tensor PCA
This work establishes a hardness partial order for planted tensor models, which is incremental but provides formal reductions that could impact theoretical computer science and machine learning by linking conjectured-hard problems.
The paper tackles the computational properties of noisy planted k-XOR and Tensor PCA by unifying them into a family of problems and building polynomial-time average-case reductions across different regimes, such as reducing conjectured-hard k-XOR instances to Tensor PCA and providing order-reducing maps like 5→4 for k-XOR.
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 $δ$. 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 \geq 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 \leq 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 = \widetildeÎ(n^{1.4})$. Taken together, these results establish a hardness partial order in the space of planted tensor models.