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.