Cheng Mao is an Assistant Professor in the School of Mathematics at Georgia Tech. His research interests can be broadly summarized as the mathematics of data science, which is a mix of mathematical statistics, applied probability, theoretical computer science, and other related fields. In recent years, his primary research focus has been on statistical inference on random graphs.
Talk: Inference of Planted Subgraphs in Random Graphs
Abstract: 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.