Jian Ding received his PhD from The University of California, Berkeley in 2011. He is currently a Chair Professor at Peking University. Ding works on probability theory with emphasis on its interactions with statistical physics, theoretical computer science as well as statistical learning theory. With various coauthors, he has made contributions to topics including random constraint satisfaction problems, random planar geometry, random field Ising models, random walk in random environments and random Schrödinger operators. Ding has received recognition including the Rollo Davidson Prize 2017 (shared with Nike Sun), an ICM invited lecture 2022 (joint with Julien Dubédat and Ewain Gwynne) and the ICCM Gold Medal 2022.

This IMS Medallion Lecture will be given at the Seminar on Stochastic Processes (SSP) 2023 meeting (March 8–11, 2023, at the University of Arizona in Tucson, USA: see https://ssp2023.math.arizona.edu/home).

Recent progress on random graph matching problems

A basic goal for random graph matching is to recover the vertex correspondence between two correlated graphs from an observation of these two unlabeled graphs. Random graph matching is an important and active topic in combinatorial statistics: on the one hand, it arises from various applied fields such as social network analysis, computer vision, computational biology and natural language processing; on the other hand, there is also a deep and rich theory that is of interest to researchers in statistics, probability, combinatorics, optimization, algorithms and complexity theory.

Recently, extensive efforts have been devoted to the study for matching two correlated Erdős–Rényi graphs, which is arguably the most classic model for graph matching. In this talk, we will review some recent progress on this front, with emphasis on the intriguing phenomenon on (the presumed) information-computation gap. In particular, we will discuss progress on efficient algorithms thanks to the collective efforts from the community. We will also point out some important future directions, including developing robust algorithms that rely on minimal assumptions on graph models and developing efficient algorithms for more realistic random graph models.

This is based on joint work with Hang Du, Shuyang Gong, Zhangsong Li, Zongming Ma, Yihong Wu and Jiaming Xu.