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/