20 problems

Low-degree conjecture. If there exist $\epsilon>0$ and $D=D(n)\geq (\log n)^{1+\epsilon}$ such that

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…

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…

Let $(\mathcal{X}_n,\mathcal{P})$ be a sequence of CLVMs, giving rise to sequences of measures $\mathbb{P}_n$ and $\mathbb{Q}_n$ on $\Omega^N$, where $N=N(n)$. Let…

Let $d$ be a degree parameter. A degree-$d$ polynomial algorithm is an algorithm represented by a polynomial of degree at most $d$, and a “robust” algorithm is an algorithm whose r…

Refined low-degree conjecture. Fix $0<\delta_1<\delta_2$. Every sequence $f=f_n$ computable in time $\exp(O(n^{\delta_1}))$ satisfies

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…

A hypothesis-testing problem compares two distributions on inputs of size $n$, and a problem is sufficiently noisy when it lies in the regime addressed by the cited low-degree fram…

Let $\mathbb{P}_{{\cal H}_0}$ and $\mathbb{P}_{{\cal H}_1}$ be a sequence of probability measures, and let $\mathsf{L}_{n}^{\leq \mathsf{D}}$ denote the degree-$\mathsf{D}$ low-deg…

Let $\P_N$ and $\Q_N$ be distributions on $\mathbb{R}^N$, and let $\chi^2(\P_N\|\Q_N):=\mathbb{E}_{\x\sim\Q_N}\left[\frac{d\P_N(\x)}{d\Q_N(\x)}\right]^2-1$. Write…

Let $\mathbb{P}$ and $\mathbb{Q}$ be the null and alternative distributions for a hypothesis-testing problem, and let $\ld(D)$ denote the low-degree likelihood-ratio quantity at po…

Let $\rho$ range over the distributions specified in the paper’s Specific Hardness Assumptions. Symmetry Conjecture. These distributions are symmetric enough for the stronger Secre…

Let $\rho$ be sufficiently symmetric, and let $p_\rho(s)$ denote the intersection-size distribution for two independent sets sampled from $\rho$. Stronger Secret Leakage Planted Cl…

Let $\Omega$ be finite or $\mathbb R$, let $k$ be fixed, and let $N=\binom nk$. Let $\nu$ be a product distribution on $\Omega^N$, let $\mu$ be another distribution on $\Omega^N$,…

Let observations lie in $\{-1,1\}^N$. For a null hypothesis $H_0$, a $D$-simple statistic is a polynomial $f$ of degree at most $D$ satisfying … Low-Degree Conjecture. For a broad…

Consider a broad class of hypothesis-testing problems $H_0$ versus $H_1$. A polynomial $f$ is a $D$-simple statistic if it has degree at most $D$ and satisfies … while…

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

Low-degree likelihood-ratio conjecture. If there exists $\varepsilon>0$ and $D=D(n)\geq(\log n)^{1+\varepsilon}$ such that

Low-degree likelihood-ratio conjecture. If $\|L_n^{\leq D(n)}\|_{L^2(\mathbb{Q}_n)}$ remains bounded as $n\to\infty$ whenever $D(n)\leq t(n)\cdot\operatorname{polylog}(n)$, then th…