Information-Theoretic Thresholds for Planted Dense Cycles
Not on the map. Why?
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.
Key facts. Cited by 1 paper in the map (data through 7 Oct 2026). Builds on 21 of its 58 references that are in the map. First posted on arXiv 1 Feb 2024.
Builds on
21 of 58 references.
References · 21
- 2019Notes on Computational Hardness of Hypothesis Testing: Predictions using the Low-Degree Likelihood Ratiocited by 82
- 2017The power of sum-of-squares for detecting hidden structurescited by 54
- 2021Settling the Sharp Reconstruction Thresholds of Random Graph Matchingcited by 45
- 2020Computational Barriers to Estimation from Low-Degree Polynomialscited by 38
- 2017Bayesian estimation from few samples: community detection and related problemscited by 28
- 2020Testing correlation of unlabeled random graphscited by 26
- 2014Testing for high-dimensional geometry in random graphscited by 25
- 2014Computational Lower Bounds for Community Detection on Random Graphscited by 21
- 2019Latent Distance Estimation for Random Geometric Graphscited by 11
- 2019Phase Transitions for Detecting Latent Geometry in Random Graphscited by 9
- 2018Hidden Hamiltonian Cycle Recovery via Linear Programmingcited by 8
- 2021Localization in 1D non-parametric latent space models from pairwise affinitiescited by 7
9 more
- 2019Consistent recovery threshold of hidden nearest neighbor graphscited by 6
- 2021Phase transition in noisy high-dimensional random geometric graphscited by 6
- 2020Community detection and percolation of information in a geometric settingcited by 5
- 2020Reconstruction of Line-Embeddings of Graphonscited by 5
- 2021A probabilistic view of latent space graphs and phase transitionscited by 5
- 2023Spectral clustering in the Gaussian mixture block modelcited by 5
- 2022Random Geometric Graph: Some recent developments and perspectivescited by 4
- 2023Detection-Recovery Gap for Planted Dense Cyclescited by 4
- 2016On Detection and Structural Reconstruction of Small-World Random Networkscited by 3
Built on by
Citing papers per year: 2024: 1.
1 paper.