21 problems

Decelle–Krzakala–Moore–Zdeborová conjecture. For the block model: (I) for all $q$, it is possible to detect communities better than random if $d\lambda^2>1$; (II) for $q\leq 4$, it…

The truncate-and-relax threshold conjecture. If $I_2(\alpha,\beta) > 1$, then

Quasirandomness conjecture. There exists a constant-degree polynomial test that distinguishes these hypotheses with high probability if and only if one of the signed subgraph count…

Let $G_1$ and $G_2$ be correlated stochastic block model graphs with community assignment $\boldsymbol{\boldsymbol{\sigma}}$, parameters $\alpha$, $\beta$, and correlation paramete…

Let $T$ be a regular tree or a Galton-Watson tree with Poisson offspring distribution, with root vertex $\rho$. Let $(T,\rho,\theta,W)$ denote the corresponding broadcast model wit…

Let $\bT_\delta$ be the noise operator that rewires $\lfloor\delta n\rfloor$ swaps of a $d$-regular graph, and let $\sG_{n,d,k,\eta}^{\,\mathrm{eq}}$ be the equitable stochastic bl…

Largest-entry conjecture. The largest entry of $\mathbf{v_2}$ satisfies

Let $0 \leq \delta \leq c$. Define $\mathbf{Q}=G(n,\kappa_1)$ for the constant kernel $\kappa_1\equiv c$, and let $\mathbf{P}=G(n,\kappa_2)$, where $\kappa_2$ equals $c+\delta$ on…

In the 2-WSBM, let $N$ be the number of vertices, $k$ the community size, and let $\gamma$ denote the signal-to-noise ratio; assume $k=o(\log N)$. For $k=2$, the model is equivalen…

Constant-community approximation conjecture. There is a constant $c$ independent of $N$, but dependent on the weights $\beta_i$, such that every $X\in\mathcal{X}_f$ is $o(n)$-close…

Let $k\in\mathbb{Z}_+$, let $p\in(0,1)^k$ be a probability distribution, and let $Q$ be a symmetric $k\times k$ matrix with nonnegative entries. Let $P$ be the diagonal matrix with…

Kesten–Stigum conjecture. For any $k\geq 2$, if $\mathrm{SNR}>1$, it is possible to detect communities in polynomial time. If $k\geq 4$, it is possible to detect communities inform…

Decelle–Krzakala–Moore–Zdeborová conjecture. If $(a-b)^2>2(a+b)$, one can almost surely find a bisection positively correlated with the original clusters; if $(a-b)^2<2(a+b)$, the…

Let $(G_1,G_2)\sim \rho$-SBM$(K,\vec{n},b,\Lambda)$, with $K$ and $\Lambda$ fixed in $n$, and let $\boldsymbol{\sigma}$ be uniformly distributed on $\Pi(n)$. Relative information-l…

Throughout, let $G(n,a/n,b/n)$ be the two-community stochastic block model with two roughly equal-sized communities, within-community connection probability $a/n$, between-communit…

Unique-fixed-point conjecture. If $mu=nu$, then this recursion has a unique fixed point for every

In the large-degree regime, let $\mu$ and $\alpha$ be the parameters appearing in the scalar density-evolution recursion, and let $h(v)$ be the function defined by that recursion.…

Under the binary symmetric stochastic block model with $\alpha$-noisy side information, let $p_{G_n}(\widehat{\sigma}_{\rm BP}^t)$ be the estimation accuracy of belief propagation a…

Let $T$ be an infinite tree with root $\rho$. In the two-state broadcast process, each vertex label $\tau_v\in\{\pm 1\}$ is generated by assigning the root a uniformly random label…

Let $\mathcal{G}(n,a/n,b/n)$ be the planted partition model with $k$ communities, where $a>b$. Let $c(k)$ be a threshold depending only on $k$. Decelle–Krzakala–Moore–Zdeborová's P…

Let $\mathcal{G}(n,a/n,b/n)$ be the sparse planted partition model with two equal-sized clusters and parameters $a>b>0$. A consistent estimator of $a$ and $b$ is an estimator whose…