Polynomial-time hardness conjecture for balanced independent sets in dense random bipartite graphs

Let $G_{\mathrm{bip}}(n,p)$ be the random bipartite graph in the online model considered in the source, let $\gamma$ be the balance parameter, and let $\alpha_{\rm COMP}$ denote the computational threshold defined earlier in the paper. Polynomial-time hardness conjecture. For any $\epsilon>0$ and $p=\Theta(1)$, no polynomial-time algorithm finds a $\gamma$-balanced independent set of size $(1+\epsilon)\alpha_{\rm COMP}$ in $G_{\mathrm{bip}}(n,p)$ whp. This conjecture concerns the computational gap for online balanced independent sets in dense random bipartite graphs; the paper's results provide rigorous evidence for the claimed threshold, while the conjecture itself remains open.