Hypergraphic planted clique detection conjecture

Equivalent formulations 1

Other statements of this same problem, merged from separate entries. Each is equivalent to the statement above — proving any one settles them all.

1. Hypergraphic planted clique detection conjecture

   Let $d\geq 2$ be a fixed integer. For a $d$-uniform hypergraph $G$, let $H_0$ denote the null distribution $G\sim\mathcal{G}_d(N,1/2)$ and let $H_1$ denote the planted-clique distribution $G\sim\mathcal{G}_d(N,1/2,\kappa)$. A test is a polynomial-time map $\phi:G\to\{0,1\}$. Hypergraphic planted clique detection conjecture. If

   $$\limsup_{N\to\infty}\frac{\log\kappa}{\log\sqrt{N}}\leq 1-\epsilon \quad\text{for any }\epsilon>0,$$

   then, for any sequence of polynomial-time tests $\{\phi\}_N$,

   $$\liminf_{N\to\infty}\mathbb{P}_{H_0}(\phi(G)=1)+\mathbb{P}_{H_1}(\phi(G)=0)>\frac12.$$

   Thus no such test can reliably distinguish the null and planted-clique models in this regime. The conjecture underlies computational lower bounds for high-order clustering; related open questions include whether hypergraphic planted clique detection is equivalently hard as ordinary planted clique detection.

   source: Rungang Han, Yuetian Luo, Miaoyan Wang and Anru R. Zhang, “Exact Clustering in Tensor Block Model: Statistical Optimality and Computational Limit”, arXiv:2012.09996 (2022).