mlsanityData to 14 Oct 2026

Detection-Recovery Gap for Planted Dense Cycles

arXiv 2302.06737 ↗First posted 13 Feb 2023math.ST cs.DS stat.MLcited by 4

Not on the map. Why?

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.

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

20 of 55 references.

References · 20

  1. 2019Notes on Computational Hardness of Hypothesis Testing: Predictions using the Low-Degree Likelihood Ratiocited by 85
  2. 2017The power of sum-of-squares for detecting hidden structurescited by 54
  3. 2020Computational Barriers to Estimation from Low-Degree Polynomialscited by 39
  4. 2018Reducibility and Computational Lower Bounds for Problems with Planted Sparse Structurecited by 35
  5. 2022The Franz-Parisi Criterion and Computational Trade-offs in High Dimensional Statisticscited by 31
  6. 2017Bayesian estimation from few samples: community detection and related problemscited by 28
  7. 2014Testing for high-dimensional geometry in random graphscited by 25
  8. 2014Computational Lower Bounds for Community Detection on Random Graphscited by 22
  9. 2019Latent Distance Estimation for Random Geometric Graphscited by 11
  10. 2019Phase Transitions for Detecting Latent Geometry in Random Graphscited by 9
  11. 2018Hidden Hamiltonian Cycle Recovery via Linear Programmingcited by 8
  12. 2021Localization in 1D non-parametric latent space models from pairwise affinitiescited by 7
8 more
  1. 2019Consistent recovery threshold of hidden nearest neighbor graphscited by 6
  2. 2021Phase transition in noisy high-dimensional random geometric graphscited by 6
  3. 2020Community detection and percolation of information in a geometric settingcited by 5
  4. 2020Reconstruction of Line-Embeddings of Graphonscited by 5
  5. 2020Estimating Rank-One Spikes from Heavy-Tailed Noise via Self-Avoiding Walkscited by 5
  6. 2021A probabilistic view of latent space graphs and phase transitionscited by 5
  7. 2022Random Geometric Graph: Some recent developments and perspectivescited by 4
  8. 2016On Detection and Structural Reconstruction of Small-World Random Networkscited by 3

Built on by

Cited by year

Citing papers per year: 2023: 1; 2024: 2; 2025: 1.

4 papers.

  1. 2023Computational Lower Bounds for Graphon Estimation via Low-degree Polynomialscited by 6
  2. 2024Information-Theoretic Thresholds for Planted Dense Cyclescited by 2
  3. 2024Information-Theoretic Thresholds for the Alignments of Partially Correlated Graphscited by 0
  4. 2025Statistical and computational challenges in rankingcited by 0