Average-case reductions for k-XOR and Tensor PCAResearch Paper
Planted noisy -XOR and Tensor PCA are two canonical average-case problems. Both have a hidden sign vector, both have a wide range of parameters where the hidden vector is determined by the data but no polynomial-time algorithm is known to find it, and both are used as hardness assumptions: -XOR for learning halfspaces, DNFs and tensor completion and in…