2 problems

the planted dense subgraph recovery conjecture. No polynomial-time algorithm $\mathcal{A}:G\to{[n]\choose k_n}$ can achieve exact recovery asymptotically.

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…