Perhaps it should be mentioned that such results originate from the normal SBM where both the information-theoretic threshold for detection, and the conjectured algorithmic threshold were studied in detail, e.g. in "Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications" by Decelle et al. Also in that case the gap between the two threshold is d (for large d). While the main contribution of the paper is theoretical, it would have been nice to see some practical demonstration of the algorithm, comparison to other algorithms (at the same time this should not be used as an argument for rejection). Evidence of the scalability of the algorithm should be presented. Minor points: While the o(), O(), \Omega() notations are rather standard I was not very familiar with the \omega() and had to look it up to be sure. Perhaps more of NIPS audience would not be familiar with those and the definition could be shortly reminded. I've read the author's feedback and took it into account in my score.

The sparse matrix estimation problem consists of estimating the distribution of an $n\times n$ matrix $Y$, from a sparsely observed single instance of this matrix where the entries of $Y$ are independent random variables. This captures a wide array of problems; special instances include matrix completion in the context of recommendation systems, graphon estimation, and community detection in (mixed membership) stochastic block models. Inspired by classical collaborative filtering for recommendation systems, we propose a novel iterative, collaborative filtering-style algorithm for matrix estimation in this generic setting. We show that the mean squared error (MSE) of our estimator converges to $0$ at the rate of $O(d 2 (pn) {-2/5})$ as long as $\omega(d 5 n)$ random entries from a total of $n 2$ entries of $Y$ are observed (uniformly sampled), $\E[Y]$ has rank $d$, and the entries of $Y$ have bounded support. The maximum squared error across all entries converges to $0$ with high probability as long as we observe a little more, $\Omega(d 5 n \ln 5(n))$ entries.