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

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.