44 problems

Let the stochastic block model have two equal-sized communities, with within-community and between-community edge probabilities $a/n$ and $b/n$, respectively. Weak recovery means o…

Fixed-point and spinodal-curve conjecture. (i) If $\lambda>1$, then $G$ has two fixed points, $0$ and $\alpha>0$; moreover, $0$ is unstable and $\alpha$ is stable. (ii) For…

Let $\mathcal{G}(n,a/n,b/n)$ be the sparse planted partition model with two equal-sized vertex classes, within-class edge probability $q=a/n$, and between-class edge probability…

Consider the stochastic block model with average degree $d$, signal parameter $\lambda$, and number of communities $q$. Weak recovery is nontrivial estimation of the community assi…

Consider the stochastic block model with parameters $d$, $\lambda$, and number of communities $q$, and let the Kesten–Stigum (KS) threshold be given by $d\lambda^2=1$. Abbe–Sandon'…

In a statistical problem with input size $n$, consider estimators that are multivariate polynomials of degree at most $D$. Low-degree conjecture. For many problems, failure of degr…

Consider the symmetric sparse stochastic block model with constant number of communities $q$, average degree $d$, signal parameter $\lambda$, spike prior $\pi$, and probability mat…

Let $f(t,\mu)$ denote the limit of the re-scaled mutual information between the signal and the observation, parametrized by $(t,\mu)\in\mathbb{R}_{\geq 0}\times\mathcal{M}_+$. Domi…

Consider the symmetric stochastic block model with $q=4$ communities, parameters $d$ and $\lambda$, and Kesten–Stigum threshold $d\lambda^2=1$. Tightness means that weak recovery i…

Consider the symmetric stochastic block model with $q=4$ communities, parameters $d$ and $\lambda$, and Kesten–Stigum threshold $d\lambda^2=1$. Tightness means that this threshold…

Dimension-one SDP threshold conjecture. The recovery threshold is conjectured to be

Recovery-threshold conjecture. If $\Delta > 2.14$, then Problem recovers the planted clusters with high probability.

Consider the stochastic block model with $q$ groups, $p_{\mathrm{in}}=\alpha d/n$, and $p_{\mathrm{out}}=d/n$. Let $d_{\mathrm{inf}}$ denote the information-theoretic threshold for…

Let $p$ denote the factorization rank in the Burer–Monteiro factorization … is benign with high probability in each of the following settings: the high-dimensional Kuramoto model,…

Vu–Abbe conjecture. Vanilla spectral algorithms are themselves good clustering algorithms for the stochastic block model.

Let $q\ge 2$ be the number of communities in the symmetric stochastic block model, and let weak recovery mean that there is an estimator whose expected Hamming error, modulo commun…

Consider the stochastic block model and compare Markov-chain Monte Carlo (MCMC) with message-passing algorithms for inference. MCMC optimality conjecture. MCMC performs as well as…

Let $\overline{F}_N$ be the finite-$N$ free energy and let $f$ be the viscosity solution of the associated infinite-dimensional Hamilton–Jacobi equation. Before characteristic line…

Let $f$ denote the unique viscosity solution of the infinite-dimensional Hamilton–Jacobi equation governing the enriched free energy, and let $\mathbf{G}_N$ and $\sigma^*$ denote t…

Let $f:[0,\infty)\times\mathcal{M}_+\to\mathbb{R}$ be the solution of the infinite-dimensional Hamilton–Jacobi equation … where $\mathcal{M}_+$ is the space of measures used in the…

Let $\overline{F}_N$ be the modified free energy, and let $f(t,\mu)$ solve the infinite-dimensional Hamilton–Jacobi equation specified by the model's enriched free energy. Free-ene…

SDP recovery conjecture. The SDP relaxation of the minimum bisection problem recovers the planted bisection whenever the minimum bisection problem does.

SDP recovery conjecture. An SDP relaxation of the minimum bisection problem achieves the information-theoretic limit for exact community recovery.

Powered adjacency recovery conjecture. Let $a,b\geq 0$ satisfy $(a-b)^2>2(a+b)$, let $r=\Theta(\sqrt{\log n})$, and let $G\sim\mathrm{SBM}(n,a,b)$. If $w$ is the eigenvector of…

Powered spectral recovery conjecture. Choose $p$ and $Q$ such that vertices from every community have the same expected degree and there is an efficient algorithm that solves weak…