2 papers
cs.CC2026
Average-Case Reductions for -XOR and Tensor PCA
Guy Bresler, Alina Harbuzova
We study the computational properties of two canonical planted average-case problems -- noisy planted -XOR and Tensor PCA -- by formally unifying them into a family of planted p…
math.ST2025
Computational Equivalence of Spiked Covariance and Spiked Wigner Models via Gram-Schmidt Perturbation
Guy Bresler, Alina Harbuzova
In this work, we show the first average-case reduction transforming the sparse Spiked Covariance Model into the sparse Spiked Wigner Model and as a consequence obtain the first com…