Before revision: 16\log{n}{nps^2}} . We improve their condition to \beta\geq\max 30\sqrt{\frac{\log n{n(1-p)^2s^2}},\frac{45\log{n}}{np(1-p)^2s^2}} . However, when p=O \sqrt{{\log n/{ns^2}}} , our improved condition still requires that \beta must increase inversely proportional to np. In order to improve the matching performance for sparse graphs, we propose a new algorithm that uses "witnesses"
After revision: 16\log{n}{nps^2}} . We improve their condition to \beta\geq\max 30\sqrt{\frac{\log n{n(1-p)^2s^2}},\frac{45\log{n}}{np(1-p)^2s^2}} . However, when p=O \sqrt{{\log n/{ns^2}}} We first analyze a simple algorithm that matches vertices based on the number of common seeds in the 1-hop neighborhoods, and then further propose a new algorithm that uses "witnesses"