Will Perkins

Subsampled Power Iteration: a Unified Algorithm for Block Models and Planted CSP's

We present an algorithm for recovering planted solutions in two well-known models, the stochastic block model and planted constraint satisfaction problems (CSP), via a common generalization in terms of random bipartite graphs. Our algorithm matches up to a constant factor the best-known bounds for…