# Information-Theoretic Thresholds for Planted Dense Cycles

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 21 of its 58 references that are in the map.
- First posted on arXiv 1 Feb 2024.

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

- [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)
- [Settling the Sharp Reconstruction Thresholds of Random Graph Matching](https://mlsanity.com/paper/2102.00082/) (2021)
- [Computational Barriers to Estimation from Low-Degree Polynomials](https://mlsanity.com/paper/2008.02269/) (2020)
- [Bayesian estimation from few samples: community detection and related problems](https://mlsanity.com/paper/1710.00264/) (2017)
- [Testing correlation of unlabeled random graphs](https://mlsanity.com/paper/2008.10097/) (2020)
- [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)
- [Spectral clustering in the Gaussian mixture block model](https://mlsanity.com/paper/2305.00979/) (2023)
- [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)
- [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)
- [Detection-Recovery Gap for Planted Dense Cycles](https://mlsanity.com/paper/2302.06737/) (2023)
- [On Detection and Structural Reconstruction of Small-World Random Networks](https://mlsanity.com/paper/1604.06474/) (2016)

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

- [Attributed Network Alignment: Statistical Limits and Efficient Algorithm](https://mlsanity.com/paper/2604.04365/) (2026)
- [Information-Theoretic Thresholds for the Alignments of Partially Correlated Graphs](https://mlsanity.com/paper/2406.05428/) (2024)

## Abstract (arXiv)

We study a random graph model for small-world networks which are ubiquitous in social and biological sciences. In this model, a dense cycle of expected bandwidth n τ, representing the hidden one-dimensional geometry of vertices, is planted in an ambient random graph on n vertices. For both detection and recovery of the planted dense cycle, we characterize the information-theoretic thresholds in terms of n, τ, and an edge-wise signal-to-noise ratio λ. In particular, the information-theoretic thresholds differ from the computational thresholds established in a recent work for low-degree polynomial algorithms, thereby justifying the existence of statistical-to-computational gaps for this problem.