Specific hardness assumptions for planted clique variants

Let $m$ and $n$ be polynomial in one another. The problems $k\textsc{-pc}(n,k,1/2)$, $\textsc{bpc}(m,n,k_m,k_n,1/2)$, $k\textsc{-bpc}(m,n,k_m,k_n,1/2)$, and $k\textsc{-hpc}^s(n,k,1/2)$ are the stated planted-clique variants. Specific Hardness Assumptions. There is no polynomial-time algorithm solving these problems, respectively, when $k=o(\sqrt n)$; when $k_n=o(\sqrt n)$ and $k_m=o(\sqrt m)$; when $k_n=o(\sqrt n)$ and $k_m=o(\sqrt m)$; and, for $s\ge3$, when $k=o(\sqrt n)$. These assumptions provide computational barriers for several secret-leakage planted-clique variants; the paper notes that the $k$-hidden-planted-clique assumption is the strongest and implies the other listed assumptions by reductions.