  We consider the algorithmic problem of finding large \textit{balanced}
independent sets in sparse random bipartite graphs, and more generally the
problem of finding independent sets with specified proportions of vertices on
each side of the bipartition. In a bipartite graph it is trivial to find an
independent set of density at least half (take one of the partition classes).
In contrast, in a random bipartite graph of average degree $d$, the largest
balanced independent sets (containing equal number of vertices from each class)
are typically of density $(2+o_d(1)) \frac{\log d}{d}$. Can we find such large
balanced independent sets in these graphs efficiently? By utilizing the overlap
gap property and the low-degree algorithmic framework, we prove that local and
low-degree algorithms (even those that know the bipartition) cannot find
balanced independent sets of density greater than $(1+\epsilon) \frac{\log
d}{d}$ for any $\epsilon>0$ fixed and $d$ large but constant. This factor $2$
statistical--computational gap between what exists and what local algorithms
can achieve is analogous to the gap for finding large independent sets in
(non-bipartite) random graphs. Our results therefor suggest that this gap is
pervasive in many models, and that hard computational problems can lurk inside
otherwise tractable ones. A particularly striking aspect of the gap in
bipartite graphs is that the algorithm achieving the lower bound is extremely
simple and can be implemented as a $1$-local algorithm and a degree-$1$
polynomial (a linear function).
