We consider a bipartite stochastic block model on vertex sets $V_1$ and $V_2$ of size $n_1$ and $n_2$ respectively, with planted partitions in each, and ask at what densities can spectral algorithms recover the partition of the smaller vertex set. The model was previously used to give a unified algorithm for random planted hypergraph partitioning and planted random k-SAT.

When $n_2 \gg n_1$, multiple thresholds emerge, and we propose a simple spectral algorithm, Diagonal Deletion SVD, which recovers the partition at a lower density than the usual SVD. We also locate a sharp threshold for detection of the partition, in the sense of the results of Mossel, Neeman, Sly and Massoulié for the stochastic block model. This gives the best known bounds for efficient recovery densities in planted k-SAT and hypergraph partitioning as well as showing a barrier to further improvement via the reduction to the bipartite block model. Joint work with Will Perkins.