14 problems

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…

Consider a detection problem on inputs of size $n$, and let degree-$D$ polynomial algorithms be the low-degree algorithm class used in the paper. An algorithm is robust in the sens…

Let $\mathbb P$ and $\mathbb Q$ be the distributions in the paper's shuffled linear regression detection problem, and let $d$, $m$, $n$, $\sigma$, and $D$ denote respectively the a…

A computational problem has a random-input model and a planted-structure model, and low degree testing is an algebraic method for distinguishing them. Low degree testing conjecture…

Let $\mathcal{Q}$ and $\mathcal{P}$ be sufficiently nice distributions, and let $\operatorname{Adv}_{\leq D}(\mathcal{Q},\mathcal{P})$ denote the degree-$D$ low-degree advantage fo…

Let $\texttt{PINES}$ denote the polynomial-time procedure discussed in the paper, and consider the latent seriation problem in which its achieved rate is $n^{3/4}$. PINES rate conj…

Let $\mathcal{Q}=G(n,q)$ be the null distribution, and let $\widetilde{\mathcal{P}}$ be a different planted distribution that contains a dense subgraph with high probability. The r…

The paper studies two kinds of computational evidence for dense subgraph detection: failure of the sum-of-squares (SoS) hierarchy and failure of low-degree polynomial tests. SoS–lo…

Let $\PP_n$ and $\QQ_n$ be “nice” sequences of distributions, let $\LL_n$ be their likelihood ratio, and let $\LL_n^{\le D_n}$ denote its degree-$D_n$ projection in $L_2(\QQ_n)$. A…

Let $n$ denote the dimension of a high-dimensional problem, and let $D$ be the degree of a polynomial algorithm. Write $n^{\widetilde{\Theta}(D)}$ for a running time up to factors…

Let $L$ be the likelihood ratio between planted and null distributions, and let $L^{\le D}$ denote its projection onto polynomials of degree at most $D$, with norm $\|L^{\le D}\|$.…

A low-degree polynomial is a polynomial test whose degree is bounded as a function of the dimension; the model compares a null distribution with a planted distribution in high-dime…

Let $t: \mathbb{N} \to \mathbb{N}$. Consider a “natural” high-dimensional testing problem specified by distributions $\mathbb{P}_N$ and $\mathbb{Q}_N$ on an observation space…

Informal low-degree conjecture. For “nice” distributions $\mathbb{P}_n$ and $\mathbb{Q}_n$, if