17 problems

Replica prediction for the single-index global maximum. Under this double limit,

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…

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…

Fix even $r$ and $\ell$ with $n\gg\ell\geq r/2$, and let $Z_S\sim\mathcal N(0,1)$ independently for each $r$-subset $S\subset[n]$. Define the Kikuchi matrix $M(\lambda)$, indexed b…

Let $p$ and $\frac{p}{2}\leq \ell < \frac{3p}{4}$ be as in the Kikuchi-matrix detection method, and let $c(p,\ell)$ denote its detection-threshold constant. WEM19's conjecture. An…

Let $k\geq 3$ and let $\gamma_n$ denote the normalized signal-to-noise parameter in tensor power iteration. The super-polynomial time conjecture asserts that the time complexity of…

Consider the order-$k$ tensor PCA model with dimension $n$ and signal-to-noise ratio $\rho$. The algorithmic threshold conjecture asserts that the minimal signal-to-noise ratio abo…

Many statistical inference problems have a range of sample sizes or signal-to-noise ratios in which information-theoretic inference of the unknown parameter is possible. These rang…

Consider the sparse Bernoulli tensor-PCA model … with $\mathbf{x}\in\mathcal{C}_{p,k}=\{0,1/\sqrt{k}\}^p\cap\mathcal{S}_{p-1}$, and let $\operatorname{MLE}$ denote the maximum-like…

Let $d$ be the tensor dimension, $k>2$ the tensor order, and $n$ the number of samples in the Tensor PCA problem. A testing or estimation procedure is computationally efficient if…

Let $\mathbf X$ and $\mathbf Y$ denote the latent signal and observations in the sparse tensor PCA Gaussian model, respectively. The Bayes-optimal estimator is…

Let $p$ be odd and fix an integer $\ell\in[\lfloor p/2\rfloor,n-\lceil p/2\rceil]$. For $S\subseteq[n]$ with $|S|=\ell$ and $T\subseteq[n]$ with $|T|=\ell+1$, define the rectangula…

Fix an integer $p$ and let $\ell$ be constant independently of $n$. Log-free performance conjecture. There exists a constant $c_p(\ell)>0$, with $c_p(\ell)\to 0$ as $\ell\to\infty$…

Let $\mathcal{S}^N$ be the sphere, let $H_0$ be the pure-noise Hamiltonian, and for $\beta>0$ let $\pi_{0,\beta}$ be the Gibbs measure with density proportional to…

Let $H_0$ denote the pure-noise Hamiltonian, let $\alpha_c(\infty)=(k-2)/2$, and consider Langevin dynamics with signal-to-noise parameter $\lambda=N^\alpha$, initialized uniformly…

Let $k$ be the tensor order, $n$ the ambient dimension, and $\beta$ the signal-to-noise parameter in the standard Gaussian tensor PCA model. Tensor PCA threshold conjecture. A nece…

Let $k$ be the tensor order, $n$ the ambient dimension, and $\beta$ the signal-to-noise parameter in the tensor PCA model. For the recursive unfolding algorithm and the original sy…