Seminar by Cheng Mao

Monday, November 11, 2024 11:30 am - 12:30 pm EST (GMT -05:00)

Probability seminar series 

Cheng Mao
Georgia Tech

Room: M3 3127


Inference of Planted Subgraphs in Random Graphs

In the study of networks, one of the central tasks is to uncover structures hidden in noisy networks. To probe the statistical and computational limits of such problems, random graph models with planted subgraphs have been proposed and studied extensively in the literature. In this talk, I will discuss recent progress in detecting and recovering subgraphs randomly planted in an Erdős–Rényi graph beyond the well-understood planted clique or dense subgraph models. In terms of methodology, I will particularly focus on computationally efficient inference via counting small subgraphs or network motifs, such as triangles and short paths. The class of subgraph-counting methods not only achieves state-of-the-art positive results but also lies within the framework of low-degree polynomial algorithms which allows matching negative results to be proved.