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

Vitaly Feldman, Will Perkins, Santosh Vempala

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 generalizat…