# Low-degree lower bounds via almost orthonormal bases

arXiv: https://arxiv.org/abs/2509.09353 · HTML: https://mlsanity.com/paper/2509.09353/

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 11 Sep 2025.

## Built on by (most cited first, 8 of 8)

- [Phase Transition for Stochastic Block Model with more than √n Communities (II)](https://mlsanity.com/paper/2511.21526/) (2025)
- [Phase Transition for Stochastic Block Model with more than √n Communities](https://mlsanity.com/paper/2509.15822/) (2025)
- [Algorithmic Contiguity from Low-Degree Heuristic II: Predicting Detection-Recovery Gaps](https://mlsanity.com/paper/2604.17410/) (2026)
- [Sharp Low-Degree Thresholds for Planted-vs-Planted Testing](https://mlsanity.com/paper/2606.05266/) (2026)
- [Statistical-computational gap in multiple Gaussian graph alignment](https://mlsanity.com/paper/2512.00610/) (2025)
- [Statistical and computational challenges in ranking](https://mlsanity.com/paper/2512.21111/) (2025)
- [Low-degree Lower bounds for clustering in moderate dimension](https://mlsanity.com/paper/2602.23023/) (2026)
- [Two-Sample Testing for Random Graphs without Vertex Correspondence](https://mlsanity.com/paper/2610.07503/) (2026)

## Abstract (arXiv)

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 mathbbP' against a null distribution mathbbP with independent components -- the standard approach is to bound the advantage using an mathbbL2(mathbbP)-orthonormal family of polynomials. However, this method breaks down for estimation tasks or more complex testing problems where mathbbP has some planted structures, so that no simple mathbbL2(mathbbP)-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 mathbbP, 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.