9 problems

Let planted dense subgraph use constant edge densities $0<q<p\le1$, with a denser planted subgraph inside a background random graph. Planted Dense Subgraph Hardness Conjecture. All…

Consider the planted dense subgraph model with adversarial edge deletions outside the planted subgraph, and let weak recovery mean producing an estimate correlated with the planted…

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

Leftover-regime conjecture. No polynomial-time algorithm exists for detecting the planted subgraph.

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…

In the planted dense subgraph model, a hidden community has size $k$ among $n$ vertices, with signal-to-noise ratio … Recovery means finding the planted community. Hidden-Community…

Community-recovery hardness conjecture. The recovery problem is computationally hard below the threshold

Let $n$ be the number of vertices and consider the planted dense subgraph model in the regime … where $c>1$ and $\alpha,\beta\in(0,1)$ are fixed constants. In the regime…

Consider the planted dense subgraph problem with deterministic planted-subgraph size $K$, and compare it with the model in which the planted size is random and concentrated near it…