[Statlist] ETH Young Data Science Researcher Seminar Zurich, Virtual Seminar by Cheng Mao, Georgia Tech

[Maurer Letizia]

Dear all

We are glad to announce the following talk in the virtual ETH Young Data Science Researcher Seminar Zurich

"Random Graph Matching: Efficient Algorithms for Recovery and Detection"
by Cheng Mao, Georgia Tech

Time: Friday, 07 May 2021, 15.00 - 16.00
Place: Zoom at https://ethz.zoom.us/j/92367940258

Abstract: Graph matching, also known as network alignment, refers to the problem of matching the vertices of two unlabeled, edge-​correlated graphs. The problem finds applications in many areas, such as computational biology, network privacy, and computer vision. In this talk, I will discuss several recent advances in efficient recovery and detection of the latent matching between the two graphs. In particular, under a correlated Erdős–Rényi model, we can recover the exact matching with high probability if the correlation between the two graphs on n vertices is at least 1-1/polyloglog(n), while the associated detection problem can be efficiently solved if the correlation is at least a constant. On the other hand, there is evidence for computational hardness when the correlation is small. Moreover, I will discuss the theoretical significance of the graph matching problem, its connection to other problems with a planted signal, and many future directions. The talk is based on joint works with Zhou Fan, Yihong Wu, Jiaming Xu, Mark Rudelson, Konstantin Tikhomirov, and Sophie H. Yu.

M. Azadkia, Y. Chen, G. Chinot, M. Löffler, A. Taeb

Seminar website: https://math.ethz.ch/sfs/news-and-events/young-data-science.html

Young Data Science Researcher Seminar Zurich – Seminar for Statistics | ETH Zurich
math.ethz.ch

	[[alternative HTML version deleted]]