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.