Cheng Mao, Georgia Tech
Geometric structures appear frequently in real-world networks, and many random graph models have been developed to incorporate latent geometries. In this talk, I will mainly discuss a random graph with a planted dense cycle of a small bandwidth, which is a variant of the Watts-Strogatz small-world model. For this random graph model with one-dimensional geometry, we characterize the information-theoretic and computational thresholds for the detection and recovery problems. In particular, a statistical-to-computational gap exists between the thresholds achieved by exponential-time algorithms and efficient algorithms based on small subgraph counts. Moreover, a detection-to-recovery gap exists between the threshold for testing the existence of the planted cycle and that for estimating the location of the cycle.
3:30pm - Pre-talk meet and greet teatime - 219 Prospect Street, 13 floor, there will be light snacks and beverages in the kitchen area.