62 problems

In the sparse symmetric stochastic block model, let $q$ be the number of equal-sized communities, let $a,b>0$ be the within-community and between-community edge parameters, and def…

Consider a generic orthogonally invariant generalized linear model and the spectrally initialized Bayes-GVAMP estimator. Bayes-GVAMP optimality conjecture. Bayes-GVAMP is optimal a…

In the single-spiked tensor model, let $N$ be the dimension and $p$ the tensor order. Consider local algorithms initialized randomly, as well as Sum-of-Squares (SoS) and spectral m…

Let $p$ be the dimension, $n$ the sample size, and $d$ the tensor order. Consider estimating the order-$d$ moment or cumulant tensors of a sub-Gaussian random vector, with consiste…

Sparse PCA threshold conjecture. There exists a critical sparsity threshold $\gamma^*\in(0,1)$ such that, if $\gamma\geq\gamma^*$, both the information-theoretic and computational…

Let $\mathbb{Q}_n$ denote the null distribution in which $\bm{A}^{(l)}\sim\bm{N}^{(l)}$ for all $l$, and let $\mathbb{P}_n$ denote the alternative in which…

Suppose $L$ i.i.d. observations $X_1,cldots,X_L$ are drawn either from the null distribution $\mathbb{Q}_n$ or from the alternative distribution $\mathbb{P}_n$. Let…

The models considered include continuous-time and discrete-time network time-series models, with computational cost referring to the time required for model fitting and prediction.…

Luo et al.'s exact recovery conjecture. This $\sqrt n$-scale boundary is optimal for polynomial-time exact recovery. The conjecture concerns the computational threshold separating…

Let $p$ be the dimension, $n$ the sample size, and $d$ the tensor order. Consider estimating order-$d$ moment or cumulant tensors of sub-Gaussian random vectors in spectral norm. E…

Low-degree conjecture. For suitably “nice” detection tasks, low-degree polynomials should match the power of all polynomial-time algorithms.

Let ${\boldsymbol{Y}}$ be the observation matrix and let ${\boldsymbol{\theta}}_*$ be the rank-one signal direction. Define … and set … Here $\rho_{\text{\tiny \rm alg}}$ is the ac…

Maillard et al.'s threshold conjecture. This condition is conjectured to be the computationally optimal weak recovery threshold: if it is violated, no polynomial-time algorithm sho…

Consider the single-index model with fixed latent dimension $k=1$, sample-to-dimension ratio $\frac{n}{d}\to\delta$, and an even link function $h$. Let weak recovery mean estimatin…

In the low-degree polynomial framework, estimators and test statistics are multivariate polynomials of degree at most $D$ in the observations; here $n$ denotes the problem size, an…

Let $d=2^n$ be the Hilbert-space dimension for an $n$-qubit system, and consider quantum state tomography in the high-dimensional regime where the ratio of the number of measuremen…

In the symmetric Tensor Principal Component Analysis model, let $x\in\{\pm1\}^n$ be an unknown signal and observe, for $i_1<i_2<\cdots<i_r$, measurements … where the noise variable…

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 problem of detecting a planted community in a dense bipartite graph, where the proposed max truncated degree test may be statistically optimal but is computationally i…

AMP optimality conjecture. For a wide class of estimation problems, AMP is conjectured to be optimal among all polynomial-time algorithms.

Consider synchronization over $SO(2)$ or over a finite group, with signal $x$ sampled uniformly from group elements, and let $L=L_n$ be the number of frequencies. Multi-frequency s…

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…

In sparse principal component analysis, let $m$ denote the sparsity level and $n$ the number of samples. In the regime $m\gg\sqrt{n}$, recovery of the planted sparse principal comp…

RIE optimality conjecture. In the denoising or universal phase, it is statistically not possible to outperform the RIE for denoising $\bX\bX^\intercal$.

A subgaussian distribution is a distribution whose one-dimensional marginals have uniformly subgaussian tails, and a mixture-clustering regime is specified by the separation betwee…