# Algorithmic Contiguity from Low-Degree Heuristic II: Predicting Detection-Recovery Gaps

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 8 of its 140 references that are in the map.
- First posted on arXiv 19 Apr 2026.

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

- [Computational Complexity of Statistics: New Insights from Low-Degree Polynomials](https://mlsanity.com/paper/2506.10748/) (2025)
- [Optimality and Sub-optimality of PCA for Spiked Random Matrices and Synchronization](https://mlsanity.com/paper/1609.05573/) (2016)
- [Low-degree lower bounds via almost orthonormal bases](https://mlsanity.com/paper/2509.09353/) (2025)
- [General Community Detection with Optimal Recovery Conditions for Multi-relational Sparse Networks with Dependent Layers](https://mlsanity.com/paper/2004.03480/) (2020)
- [Randomstrasse101: Open Problems of 2024](https://mlsanity.com/paper/2504.20539/) (2025)
- [Phase Transition for Stochastic Block Model with more than √n Communities](https://mlsanity.com/paper/2509.15822/) (2025)
- [Fundamental Limits of Community Detection in Contextual Multi-Layer Stochastic Block Models](https://mlsanity.com/paper/2602.08173/) (2026)
- [Low-Degree Method Fails to Predict Robust Subspace Recovery](https://mlsanity.com/paper/2603.02594/) (2026)

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

- [Sharp Low-Degree Thresholds for Planted-vs-Planted Testing](https://mlsanity.com/paper/2606.05266/) (2026)

## Abstract (arXiv)

The low-degree polynomial framework has emerged as a powerful tool for providing evidence of statistical-computational gaps in high-dimensional inference. For detection problems, the standard approach bounds the low-degree advantage through an explicit orthonormal basis. However, this method does not extend naturally to estimation tasks, and thus fails to capture the detection-recovery gap phenomenon that arises in many high-dimensional problems. Although several important advances have been made to overcome this limitation citeSW22, SW25, CGGV25+, the existing approaches often rely on delicate, model-specific combinatorial arguments. In this work, we develop a general approach for obtaining conditional computational lower bounds for recovery problems from mild bounds on low-degree testing advantage. Our method combines the notion of algorithmic contiguity in citeLi25 with a cross-validation reduction in citeDHSS25 that converts successful recovery into a hypothesis test with lopsided success probabilities. In contrast to prior unconditional lower bounds, our argument is conceptually simple, flexible, and largely model-independent. We apply this framework to several canonical inference problems, including planted submatrix, planted dense subgraph, stochastic block model, multi-frequency angular synchronization, orthogonal group synchronization, and multi-layer stochastic block model. In the first three settings, our method recovers existing low-degree lower bounds for recovery in citeSW22, SW25 via a substantially simpler argument. In the latter three, it gives new evidence for conjectured computational thresholds including the persistence of detection-recovery gaps. Together, these results suggest that mild control of low-degree advantage is often sufficient to explain computational barriers for recovery in high-dimensional statistical models.