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

Guy Bresler, Alina Harbuzova

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 p…