# Sharp Low-Degree Thresholds for Planted-vs-Planted Testing

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 7 of its 41 references that are in the map.
- First posted on arXiv 3 Jun 2026.

## Builds on (most cited first, 7 of 7)

- [Computational Complexity of Statistics: New Insights from Low-Degree Polynomials](https://mlsanity.com/paper/2506.10748/) (2025)
- [Low-degree lower bounds via almost orthonormal bases](https://mlsanity.com/paper/2509.09353/) (2025)
- [Community Detection in Random Networks](https://mlsanity.com/paper/1302.7099/) (2013)
- [Computational Lower Bounds for Correlated Random Graphs via Algorithmic Contiguity](https://mlsanity.com/paper/2502.09832/) (2025)
- [Low degree conjecture implies sharp computational thresholds in stochastic block model](https://mlsanity.com/paper/2502.15024/) (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)

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

- [Two-Sample Testing for Random Graphs without Vertex Correspondence](https://mlsanity.com/paper/2610.07503/) (2026)

## Abstract (arXiv)

We establish the first sharp thresholds for low-degree polynomial tests in planted-vs-planted settings, where the goal is to determine with vanishing error which of two structured planted mechanisms generated the observed data. We prove matching low-degree upper and lower bounds for counting communities in the planted submatrix and planted dense subgraph models. The resulting testing threshold coincides, down to the sharp constant, with the known low-degree recovery threshold. In contrast, the task of weak testing, where the goal is to outperform random guessing, does not have a sharp threshold but rather a smooth transition, which we identify. To prove our results, we develop a framework for planted-vs-planted testing that builds on a latent-variable expansion originating in low-degree recovery and employs new methods to identify and prune non-signal contributions.