On the hardness of finding balanced independent sets in random bipartite graphs

Will Perkins, Yuzhou Wang

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