S&DS Seminar: Cheng Mao, “Learning One-Dimensional Geometry in Random Graphs”


Yale Institute for Foundations of Data Science, Kline Tower 13th Floor, Room 1327, New Haven, CT 06511

Speaker: Cheng Mao,
School of Mathematics, Georgia Institute of Technology

Monday, October 16, 2023
3:30 PM – Pre-Talk Meet & Greet (Kitchen)
4:00 PM – Talk (Room #1327)

Location: Yale Institute for Foundations of Data Science
Kline Tower, 13th Floor
219 Prospect Street, New Haven ,CT 06511

Title: Learning One-Dimensional Geometry in Random Graphs

Abstract: 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.

Website: https://cmao35.math.gatech.edu/