Abstract
The Graph Matching problem is a robust version of the Graph Isomorphism problem: given two not-necessarily-isomorphic graphs, the goal is to find a permutation of the vertices which maximizes the number of common edges. We study a popular average-case variant, giving the first quasi-polynomial time algorithm for O(1)-correlated random graphs, where previously only sub-exponential time algorithms were known. Our algorithm relies on a careful use of logarithmic-sized subgraph statistics. Based on joint work with Boaz Barak, Chi-Ning Chou, Zhixian Lei, and Yueqi Sheng.