{"ID":2860988,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2510.03061","arxiv_id":"2510.03061","title":"Smooth Trade-off for Tensor PCA via Sharp Bounds for Kikuchi Matrices","abstract":"In this work, we revisit algorithms for Tensor PCA: given an order-$r$ tensor of the form $T = G+λ\\cdot v^{\\otimes r}$ where $G$ is a random symmetric Gaussian tensor with unit variance entries and $v$ is an unknown boolean vector in $\\{\\pm 1\\}^n$, what's the minimum $λ$ at which one can distinguish $T$ from a random Gaussian tensor and more generally, recover $v$? As a result of a long line of work, we know that for any $\\ell \\in \\N$, there is a $n^{O(\\ell)}$ time algorithm that succeeds when the signal strength $λ\\gtrsim \\sqrt{\\log n} \\cdot n^{-r/4} \\cdot \\ell^{1/2-r/4}$. The question of whether the logarithmic factor is necessary turns out to be crucial to understanding whether larger polynomial time allows recovering the signal at a lower signal strength. Such a smooth trade-off is necessary for tensor PCA being a candidate problem for quantum speedups[SOKB25]. It was first conjectured by [WAM19] and then, more recently, with an eye on smooth trade-offs, reiterated in a blogpost of Bandeira. In this work, we resolve these conjectures and show that spectral algorithms based on the Kikuchi hierarchy \\cite{WAM19} succeed whenever $λ\\geq Θ_r(1) \\cdot n^{-r/4} \\cdot \\ell^{1/2-r/4}$ where $Θ_r(1)$ only hides an absolute constant independent of $n$ and $\\ell$. A sharp bound such as this was previously known only for $\\ell \\leq 3r/4$ via non-asymptotic techniques in random matrix theory inspired by free probability.","short_abstract":"In this work, we revisit algorithms for Tensor PCA: given an order-$r$ tensor of the form $T = G+λ\\cdot v^{\\otimes r}$ where $G$ is a random symmetric Gaussian tensor with unit variance entries and $v$ is an unknown boolean vector in $\\{\\pm 1\\}^n$, what's the minimum $λ$ at which one can distinguish $T$ from a random G...","url_abs":"https://arxiv.org/abs/2510.03061","url_pdf":"https://arxiv.org/pdf/2510.03061v1","authors":"[\"Pravesh K. Kothari\",\"Jeff Xu\"]","published":"2025-10-03T14:43:19Z","proceeding":"cs.DS","tasks":"[\"cs.DS\",\"cs.CC\"]","methods":"[]","has_code":false}