10 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…

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…

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…

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 $\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$,…

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 $\|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…