Event time:

Friday, October 4, 2019 - 11:00am

Location:

Rm 107, 24 Hillhouse Ave.

Speaker:

Harry Zhou

Speaker affiliation:

Henry Ford II Professor of Statistics and Data Science, Yale University

Event description:

Theory Seminar

Abstract: We’ll discuss some recent work with Yihong Wu and Jiaming Xu on the “graph matching” problem of identifying the vertex matching between two graphs with correlated edges. We propose a simple spectral algorithm, which is related to a popular convex relaxation approach for this problem and also to the behavior of eigenvector moment flows for random matrices. We’ll describe a theoretical result establishing conditions under which this algorithm exactly recovers the vertex matching between two correlated Erdos-Renyi random graphs, and discuss some of the ideas of its proof and some open questions.