HPDS recovery computational hardness conjecture

Let $G\sim\mathcal{G}_d(N,\kappa,q_1,q_2)$ be a hypergraphic planted dense subgraph with $q_1>q_2$, adjacency tensor ${\mathbfcal A}$, and recovery error $\mathcal{E}_{{\rm HPDS}_R}$. HPDS recovery conjecture. If

$$\liminf_{N\to\infty}\log_N\kappa\geq\frac12$$

and

$$\limsup_{N\to\infty}\log_N\left(\frac{\kappa^{d-1}(q_1-q_2)}{\sqrt{q_2(1-q_2)}}\right)<\frac d2-\frac12,$$

then every randomized polynomial-time algorithm $\{\phi_N\}$ satisfies

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

This conjecture says that the signal-to-noise requirement sufficient for the paper’s Aggregated-SVD recovery guarantee is also necessary for computationally efficient recovery in the stated regime. The source does not provide a resolution.