Information-Theoretic Thresholds for Planted Dense Cycles

作     者：Mao, Cheng Wein, Alexander S. Zhang, Shenduo 

作者机构：Georgia Inst Technol Sch Math Atlanta GA 30332 USA Univ Calif Davis Dept Math Davis CA 95616 USA 

出 版 物：《IEEE TRANSACTIONS ON INFORMATION THEORY》 (IEEE Trans. Inf. Theory)

年 卷 期：2025年第71卷第2期

页      面：1266-1282页

核心收录：

学科分类：0808[工学-电气工程] 08[工学] 0701[理学-数学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：NSF [DMS-2053333  DMS-2210734  DMS-2338062] 

主　　题：Information theory Image edge detection Polynomials Biological system modeling Bandwidth Computational efficiency Signal to noise ratio Geometry Prediction algorithms Lower bound Random graphs network theory graphs and networks information theory statistics geometrical problems and computations computations on discrete structures 

摘      要：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 tau , 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, tau , and an edge-wise signal-to-noise ratio lambda . 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.