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

Understand

We present an algorithm for recovering planted solutions in two well-known models, the stochastic block model and planted constraint satisfaction problems, via a common generalization in terms of random bipartite graphs.

• Our algorithm matches up to a constant factor the best-known bounds for the number of edges (or constraints) needed for perfect recovery and its running time is linear in the number of edges used.
• The time complexity is significantly better than both spectral and SDP-based approaches.
• The main contribution of the algorithm is in the case of unequal sizes in the bipartition (corresponding to odd uniformity in the CSP).