11 problems

The Gaussian Planted Submatrix problem has signal parameter $\beta$, while the Planted Clique problem is obtained from a centered Erdős–Rényi adjacency matrix with an inserted cliq…

the $k$-planted clique conjecture. If $G$ is an instance of $k\textsc{-PC}_D(n,k_n,p)$, then

Let $p\in(0,1)$ be constant. For each $n$, let $A_n:G_n\to\{0,1\}$ be a randomized polynomial-time algorithm, and let $k_n$ be a sequence of positive integers satisfying … For the…

Let $H$ be an order-$K$ hypergraph in the HPC detection problem, with null distribution $H_0:H\sim\mathcal{H}_K(p,1/2)$ and planted-clique alternative…

Hypergraph planted clique conjecture. Suppose that $p=1/2$ and that $D\geq 2$ is a fixed integer. If

Let $\mathcal{G}_d(N,1/2,\kappa)$ be the hypergraphic planted clique model on $N$ vertices with fixed integer $d\geq2$, and let $\mathcal{E}_{{\rm HPC}_D}$ denote the sum of Type-I…

Let $\rho$ be sufficiently symmetric, and let $p_\rho(s)$ denote the intersection-size distribution for two independent sets sampled from $\rho$. Stronger Secret Leakage Planted Cl…

Let $m$ and $n$ be polynomial in one another. The problems $k\textsc{-pc}(n,k,1/2)$, $\textsc{bpc}(m,n,k_m,k_n,1/2)$, $k\textsc{-bpc}(m,n,k_m,k_n,1/2)$, and…

Let $\rho$ be a distribution on $k$-subsets of $[n]$, and let $p_\rho(s)=\mathbb P_{S,S'\sim\rho^{\otimes 2}}[|S\cap S'|=s]$ be the intersection-size probability mass function. Let…

Fix a constant $p\in(0,1)$. Let $n_t$ and $k_t$ be increasing sequences of positive integers such that $k_t=o(\sqrt{n_t})$ and $k_t$ divides $n_t$, and let … be a sequence of rando…

Landscape conjecture. Suppose … If $k=o(\sqrt n)$, then: