The $k$-partite planted clique conjecture

Fix a constant $p\in(0,1)$. Let $n_t$ and $k_t$ be increasing sequences of positive integers such that $k_t=o(\sqrt{n_t})$ and $k_t$ divides $n_t$, and let

$$\mathcal{A}_t:\mathcal{G}_{n_t}\to\{0,1\}$$

be a sequence of randomized polynomial-time algorithms. Under $H_0$, $G$ is sampled from the null distribution, while under $H_1$ it is sampled from the $k_t$-partite planted-clique distribution $k\text{-pc}(n_t,k_t,p)$. $k$-partite planted clique conjecture. If $G_t$ is an instance of $k\text{-pc}(n_t,k_t,p)$, then

$$\liminf_{t\to\infty}\left(\mathbb{P}_{H_0}[\mathcal{A}_t(G)=1]+\mathbb{P}_{H_1}[\mathcal{A}_t(G)=0]\right)\geq 1.$$

Thus no such sequence of algorithms distinguishes the planted and null distributions with asymptotic error sum below $1$; this is the formal hardness assumption used by the paper's reductions, and the source gives no resolution.