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 : Our algorithm associates each vertex with a signature vector using a multistage procedure and then matches a pair of vertices from the two graphs if their signature vectors are close to each other. We 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.