{"ID":2872170,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2509.09353","arxiv_id":"2509.09353","title":"Low-degree lower bounds via almost orthonormal bases","abstract":"Low-degree polynomials have emerged as a powerful paradigm for providing evidence of statistical-computational gaps across a variety of high-dimensional statistical models [Wein25]. For detection problems -- where the goal is to test a planted distribution $\\mathbb{P}'$ against a null distribution $\\mathbb{P}$ with independent components -- the standard approach is to bound the advantage using an $\\mathbb{L}^2(\\mathbb{P})$-orthonormal family of polynomials. However, this method breaks down for estimation tasks or more complex testing problems where $\\mathbb{P}$ has some planted structures, so that no simple $\\mathbb{L}^2(\\mathbb{P})$-orthogonal polynomial family is available. To address this challenge, several technical workarounds have been proposed [SW22,SW25], though their implementation can be delicate. In this work, we propose a more direct proof strategy. Focusing on random graph models, we construct a basis of polynomials that is almost orthonormal under $\\mathbb{P}$, in precisely those regimes where statistical-computational gaps arise. This almost orthonormal basis not only yields a direct route to establishing low-degree lower bounds, but also allows us to explicitly identify the polynomials that optimize the low-degree criterion. This, in turn, provides insights into the design of optimal polynomial-time algorithms. We illustrate the effectiveness of our approach by recovering known low-degree lower bounds, and establishing new ones for problems such as hidden subcliques, stochastic block models, and seriation models.","short_abstract":"Low-degree polynomials have emerged as a powerful paradigm for providing evidence of statistical-computational gaps across a variety of high-dimensional statistical models [Wein25]. For detection problems -- where the goal is to test a planted distribution $\\mathbb{P}'$ against a null distribution $\\mathbb{P}$ with ind...","url_abs":"https://arxiv.org/abs/2509.09353","url_pdf":"https://arxiv.org/pdf/2509.09353v2","authors":"[\"Alexandra Carpentier\",\"Simone Maria Giancola\",\"Christophe Giraud\",\"Nicolas Verzelen\"]","published":"2025-09-11T11:07:36Z","proceeding":"stat.ML","tasks":"[\"stat.ML\",\"cs.LG\"]","methods":"[]","has_code":false}