{"id":"arxiv/2601.19016","url":"https://arxiv.org/abs/2601.19016","tags":["cs.CC","cs.CR","math.PR","math.ST"],"score":0,"title":"Average-Case Reductions for $k$-XOR and Tensor PCA","domain":"cs.CC","source":"arxiv","authors":["Guy Bresler","Alina Harbuzova"],"reviews":0,"subject":"cs.CC","summary":"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…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-01-26","reactions":{}}