7 problems

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…

Optimal estimation rate conjecture. The computationally optimal error rate is

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…

Consider a testing problem in the asymptotic setting, with degree-$D$ polynomial tests used as a proxy for computationally efficient algorithms. Strong separation means … while wea…

Fix parameters $(\lambda,s)$ in the correlated Erdős–Rényi model $\mathcal{G}(n,\lambda/n,s)$. One-sided correlation detection in trees is said to fail when none of the equivalent…

Refined low-degree conjecture. If there exists a polynomial-time algorithm that strongly distinguishes $(\mathsf{P}_n)$ and $(\mathsf{Q}_n)$, then

Fix $\pi\in\mathcal P_2(\mathbb R)$, $\delta\in(0,\infty)$, and $\sigma>0$. Consider sequences of dimensions, Gaussian design matrices, coefficient vectors, and noise vectors satis…