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

arXiv:2601.19016v1 Announce Type: new
Abstract: We study two canonical planted average-case problems — noisy $kmathsf{text{-}XOR}$ and Tensor PCA — and relate their computational properties via poly-time average-case reductions. In fact, we consider a emph{family of problems} that interpolates between $kmathsf{text{-}XOR}$ and Tensor PCA, allowing intermediate densities and signal levels. We introduce two emph{densifying} reductions that increase the number of observed entries while controlling the decrease in signal, and, in particular, reduce any $kmathsf{text{-}XOR}$ instance at the computational threshold to Tensor PCA at the computational threshold. Additionally, we give new order-reducing maps (e.g., $5to 4$ $kmathsf{text{-}XOR}$ and $7to 4$ Tensor PCA) at fixed entry density.