Recent progress on random graph matching problems
Part of the Oxford Discrete Maths and Probability Seminar, held via Zoom. Please see the seminar website for details.
Abstract
In this talk, I will review some recent progress on random graph matching problems, that is, to recover the vertex correspondence between a pair of correlated random graphs from the observation of two unlabelled graphs. In this talk, I will touch issues of information threshold, efficient algorithms as well as complexity theory. This is based on joint works with Hang Du, Shuyang Gong and Zhangsong Li.