Speaker: Jiaming Xu (Duke University)

Title: Recent advances on random graph matching

Abstract:
Random graph matching aims to recover the hidden vertex correspondence between two random graphs from correlated edge connections. This is a ubiquitous problem arising in a variety of applications across diverse fields such as network privacy, computational biology, computer vision, and natural language processing. The problem is also deep and rich in theory, involving the delicate interplay of algorithms, complexity, and information limits.  Recently, extensive efforts have been devoted to the study of matching two correlated Erdős–Rényi graphs and exciting progress have been made, thanks to collective efforts from a wide research community. The speaker in his talk will present an overview, recent results, and important future directions on this topic. Based on joint work with Cheng Mao (Georgia Tech), Yihong Wu (Yale), and Sophie H. Yu (Stanford).