版权所有:内蒙古大学图书馆 技术提供:维普资讯• 智图
内蒙古自治区呼和浩特市赛罕区大学西街235号 邮编: 010021
作者机构: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.