30 problems

Carpentier's motif-counting conjecture. If

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…

NFM strong-node containment conjecture. With probability not converging to $0$ as $n\to\infty$, $\ell_2$-norm-diag returns exactly $k$ disjoint clusters $V_1',\dots,V_k'$ such that…

NFM separated-eigenvector conjecture. There exists a scalar $t(k,\bm{\alpha})\in(0.5,1/\sqrt{2})$ such that, for every $j\in[k]$, with probability not converging to $0$ as…

NFM exact-recovery impossibility conjecture. No algorithm can exactly recover the true clusters in $G$ with probability not converging to $0$ as $n\to\infty$.

Let $C^0$ be a cycle of length $k$ with its signed cycle statistic $\kappa_{C^0}$, and let $\mathcal{G}(n,p,d)$ denote the noisy high-dimensional random geometric graph model witho…

Let $k$ and $p$ be fixed, let $\mathcal{G}(n,p,d)$ denote the noisy high-dimensional random geometric graph model without edge subsampling, and let $\tau_{[k]}$ be the signed $k$-c…

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…

Spectral meta-algorithm conjecture. For any $s$ and $r$ such that $\mathrm{GBM}(n,s,t)$ has a giant component, there exists $\delta>1/2$ such that the spectral meta-algorithm recov…

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…

Subpolynomial-power failure conjecture. There exists $s_0>0$ such that, for all $m>0$, $s\geq s_0$, $t>0$, and $r=n^{o(1)}$, the algorithm that finds the second-largest-eigenvalue…

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…

Powered adjacency conjecture. For all $m>0$, $s>0$, $t>0$, and $0<r'<1/2$, the algorithm that finds the eigenvector of $A^{(r'd)}$ with the second-largest eigenvalue and then divid…

Nonbacktracking failure conjecture. Computing the eigenvector of $B$ with the second-largest eigenvalue and dividing the vertices into those with above-median and below-median sums…

Powered adjacency conjecture. Let $s,t\geq 0$ and suppose $\mathrm{GBM}(n,s,t)$ has a giant component. Taking the second-largest eigenvector of $A^{(r)}$, with…

Weak recovery threshold conjecture. Let $s,t\geq 0$ and suppose $\mathrm{GBM}(n,s,t)$ has a giant component. Weak recovery is efficiently solvable in $\mathrm{GBM}(n,s,t)$ if and o…

Sharp large-time behavior conjecture. For $\tau$ fixed,

For any $\lambda>0$, $d\in\mathbb{N}$, and $0\leq b<a\leq 1$, let $\nu_d$ denote the volume of the unit Euclidean ball in $d$ dimensions, and let…

Let $A$ be the adjacency matrix of a realization from the directed Chung–Lu model with expected in-degree and out-degree vectors $\mathbf{a}$ and $\mathbf{b}$, respectively, and le…

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…

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…

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…

Decelle et al.'s computational impossibility conjecture. Irrespective of $k$, if $\operatorname{SNR}<1$, it is impossible to detect communities in polynomial time. This is the comp…

Let $(X,G)$ be drawn from the stochastic block model $\operatorname{SBM}(n,k,a,b)$: $X$ is uniformly drawn among partitions of $[n]$ into $k$ balanced clusters, and $G$ has vertex…