Subsampled Power Iteration: A Unified Algorithm for Block Models and Planted CSP's
summary
Proposes Subsampled Power Iteration that partitions edges into ~10 log n independent subgraphs and runs power iteration on each, taking independent subsamples and a majority vote of sign vectors to produce the partition. Proves exact recovery with O((sqrt(n1 n2) log n)/(delta−1)^2) edges for bipartite planted partitions, and O(n^{r/2} log n) clauses for planted k‑CSPs where r is the nonzero Fourier degree. Algorithm runs in time linear in input size and succeeds with high probability under the stated bounds.
AI-written summary · about