6 problems

Planted clique hypothesis. The ${\sf PC}$ problem cannot be solved in polynomial time for $k=o(\sqrt{n})$ when $\gamma=\frac12$.

Let $V$ be a passive or active fermionic linear-optics circuit initialized in the state $\left|\Psi_{\mathrm{in}}\right>$, let $\mathbf{x}_0$ be a fiducial outcome, and 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…

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

Let $G$ be an Erdős–Rényi graph sampled from $\mathcal{G}(n,1/2)$, with a clique of size $k=o(\sqrt n)$ planted uniformly at random. Planted clique conjecture. There is no polynomi…

Let $\mathcal{G}(n,\kappa)$ be a random graph on $n$ vertices. Under $H_0$, every edge is included independently with probability $\frac{1}{2}$. Under $H_1$, every edge is included…