HPC detection computational hardness conjecture

Let $\mathcal{G}_d(N,1/2,\kappa)$ be the hypergraphic planted clique model on $N$ vertices with fixed integer $d\geq2$, and let $\mathcal{E}_{{\rm HPC}_D}$ denote the sum of Type-I and Type-II errors of a test. HPC detection conjecture. If, for some $\tau>0$,

$$\limsup_{N\to\infty}\frac{\log\kappa}{\log\sqrt{N}}\leq1-\tau,$$

then every sequence of polynomial-time tests $\{\phi_N\}$ satisfies

$$\liminf_{N\to\infty}\mathcal{E}_{{\rm HPC}_D}(\phi_N({\mathbfcal A}))>\frac12.$$

The conjecture asserts computational hardness below the square-root clique-size scale. Exhaustive search gives the statistical threshold, while spectral methods reach the square-root scale; the source notes that whether HPC detection is equivalently hard as planted-clique detection remains open.