# Detection-Recovery Gap for Planted Dense Cycles

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 20 of its 55 references that are in the map.
- First posted on arXiv 13 Feb 2023.

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

- [Notes on Computational Hardness of Hypothesis Testing: Predictions using the Low-Degree Likelihood Ratio](https://mlsanity.com/paper/1907.11636/) (2019)
- [The power of sum-of-squares for detecting hidden structures](https://mlsanity.com/paper/1710.05017/) (2017)
- [Computational Barriers to Estimation from Low-Degree Polynomials](https://mlsanity.com/paper/2008.02269/) (2020)
- [Reducibility and Computational Lower Bounds for Problems with Planted Sparse Structure](https://mlsanity.com/paper/1806.07508/) (2018)
- [The Franz-Parisi Criterion and Computational Trade-offs in High Dimensional Statistics](https://mlsanity.com/paper/2205.09727/) (2022)
- [Bayesian estimation from few samples: community detection and related problems](https://mlsanity.com/paper/1710.00264/) (2017)
- [Testing for high-dimensional geometry in random graphs](https://mlsanity.com/paper/1411.5713/) (2014)
- [Computational Lower Bounds for Community Detection on Random Graphs](https://mlsanity.com/paper/1406.6625/) (2014)
- [Latent Distance Estimation for Random Geometric Graphs](https://mlsanity.com/paper/1909.06841/) (2019)
- [Phase Transitions for Detecting Latent Geometry in Random Graphs](https://mlsanity.com/paper/1910.14167/) (2019)
- [Hidden Hamiltonian Cycle Recovery via Linear Programming](https://mlsanity.com/paper/1804.05436/) (2018)
- [Localization in 1D non-parametric latent space models from pairwise affinities](https://mlsanity.com/paper/2108.03098/) (2021)
- [Consistent recovery threshold of hidden nearest neighbor graphs](https://mlsanity.com/paper/1911.08004/) (2019)
- [Phase transition in noisy high-dimensional random geometric graphs](https://mlsanity.com/paper/2103.15249/) (2021)
- [Community detection and percolation of information in a geometric setting](https://mlsanity.com/paper/2006.15574/) (2020)
- [Reconstruction of Line-Embeddings of Graphons](https://mlsanity.com/paper/2007.06444/) (2020)
- [Estimating Rank-One Spikes from Heavy-Tailed Noise via Self-Avoiding Walks](https://mlsanity.com/paper/2008.13735/) (2020)
- [A probabilistic view of latent space graphs and phase transitions](https://mlsanity.com/paper/2110.15886/) (2021)
- [Random Geometric Graph: Some recent developments and perspectives](https://mlsanity.com/paper/2203.15351/) (2022)
- [On Detection and Structural Reconstruction of Small-World Random Networks](https://mlsanity.com/paper/1604.06474/) (2016)

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

- [Computational Lower Bounds for Graphon Estimation via Low-degree Polynomials](https://mlsanity.com/paper/2308.15728/) (2023)
- [Information-Theoretic Thresholds for Planted Dense Cycles](https://mlsanity.com/paper/2402.00305/) (2024)
- [Information-Theoretic Thresholds for the Alignments of Partially Correlated Graphs](https://mlsanity.com/paper/2406.05428/) (2024)
- [Statistical and computational challenges in ranking](https://mlsanity.com/paper/2512.21111/) (2025)

## Abstract (arXiv)

Planted dense cycles are a type of latent structure that appears in many applications, such as small-world networks in social sciences and sequence assembly in computational biology. We consider a model where a dense cycle with expected bandwidth n τ and edge density p is planted in an ErdHos-R'enyi graph G(n,q). We characterize the computational thresholds for the associated detection and recovery problems for the class of low-degree polynomial algorithms. In particular, a gap exists between the two thresholds in a certain regime of parameters. For example, if n-3/4 ll τ ll n-1/2 and p = C q = Theta(1) for a constant C>1, the detection problem is computationally easy while the recovery problem is hard for low-degree algorithms.