I want to find a $k$ by $r$ biclique hidden in an $M$ by $N$ random bipartite graph where edges are present with probability $p \in [0,1]$. I am specifically interested in $p \ll 1$, and large values of $k$ and $r$, where the chance of having biclique by random chance is $0$.
I know that algorithms like Bron-Kerbosch can be modified to solve this problem, but their run-time is not well-bounded, and they do not utilize the fact that $p$ is very small.
Is there any way to solve this problem for small values of $p$?
