  We consider a bipartite stochastic block model on vertex sets $V_1$ and
$V_2$, with planted partitions in each, and ask at what densities efficient
algorithms can recover the partition of the smaller vertex set.
  When $|V_2| \gg |V_1|$, multiple thresholds emerge. We first locate a sharp
threshold for detection of the partition, in the sense of the results of
\cite{mossel2012stochastic,mossel2013proof} and \cite{massoulie2014community}
for the stochastic block model. We then show that at a higher edge density, the
singular vectors of the rectangular biadjacency matrix exhibit a localization /
delocalization phase transition, giving recovery above the threshold and no
recovery below. Nevertheless, we propose a simple spectral algorithm, Diagonal
Deletion SVD, which recovers the partition at a nearly optimal edge density.
  The bipartite stochastic block model studied here was used by
\cite{feldman2014algorithm} to give a unified algorithm for recovering planted
partitions and assignments in random hypergraphs and random $k$-SAT formulae
respectively. Our results give the best known bounds for the clause density at
which solutions can be found efficiently in these models as well as showing a
barrier to further improvement via this reduction to the bipartite block model.
