The planted clique detection conjecture

Let $p\in(0,1)$ be constant. For each $n$, let $A_n:G_n\to\{0,1\}$ be a randomized polynomial-time algorithm, and let $k_n$ be a sequence of positive integers satisfying

$$\limsup_{n\to\infty}\log_n k_n<\frac{1}{2}.$$

For the planted clique detection problem, with null hypothesis $H_0:G\sim G(n,p)$ and alternative hypothesis $H_1:G\sim G(n,k_n,p)$, the planted clique detection conjecture. Every such sequence of algorithms satisfies

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

This is the standard planted-clique hardness assumption underlying reductions for statistical-computational gaps; it asserts that polynomial-time algorithms cannot achieve nontrivial detection when the planted clique has size $n^{\beta}$ with $\beta<1/2$.