Before revision:  In this work, we propose a new algorithm for graph matching and show that, for two Erdo s-R\'enyi graphs with edge correlation 1-\alpha, our algorithm recovers the underlying matching  with high probability when \alpha \le 1 / (\log \log n)^C, where n is the number of vertices in each graph and C denotes a positive universal constant.
After revision:  In this work, we propose a new algorithm for graph matching and show that, for two Erdo s-R\'enyi graphs with edge correlation 1-\alpha, our algorithm recovers the underlying matching exactly with high probability when \alpha \le 1 / (\log \log n)^C, where n is the number of vertices in each graph and C denotes a positive universal constant.