(Nearly) Efficient Algorithms for the Graph Matching Problem on Correlated Random Graphs

Wegivethe first efficient algorithms proven to succeed in the correlated Erdös-Rényi model (Pedarsani and Grossglauser, 2011). Specifically, we give apolynomial time algorithm for thegraphsimilarity/hypothesis testingtaskwhich worksforeveryconstant level of correlation between the two graphs that can be arbitrarily close to zero. We also give a quasi-polynomial (nO(logn) time) algorithm for thegraph matching task of recovering the permutation minimizing the symmetric difference in this model.