4 problems

Let $(\Gamma_n)_n$ be a sequence of planted subgraphs in the recovery model, and suppose there is a gap between the information-theoretic limit and the performance of the proposed…

Let $\Gamma_n$ be a complete bipartite planted subgraph with $k_{\mathsf{L}}$ left vertices and $k_{\mathsf{R}}$ right vertices, in an ambient graph on $n$ vertices. Complete bipar…

Fix a sequence of subgraphs $\Gamma=(\Gamma_n)_n$, assume $p_n,q_n=\Theta(1)$, and consider the exact-recovery condition for the likelihood peeling algorithm … for any…

Let $Gamma$ be a graph family and consider the detection problem in the parameter region where the scan test succeeds, while the count and maximum-degree tests fail. Scan-only hard…