9 problems

Carpentier's motif-counting conjecture. If

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

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,…

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…

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…

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 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…