25 problems

Let $\mathbb P$ and $\mathbb Q$ be probability measures for a high-dimensional hypothesis-testing problem based on $\mathsf Y\in\mathbb R^N$, with $N=N_n$ and parameters scaling wi…

Constrained moment-matching lower-bound conjecture.

Quasirandomness conjecture. There exists a constant-degree polynomial test that distinguishes these hypotheses with high probability if and only if one of the signed subgraph count…

Consider asymptotic hypothesis-testing problems between probability measures $\mathbb P$ and $\mathbb Q$. For degree at most $D$, define the low-degree advantage by … Here…

Let $G_n$ be the final snapshot of a preferential attachment network on $n$ vertices, and suppose the changepoint is in the late-change regime $\tau_n=n-\Delta$ with…

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

Generalized quantum Stein's lemma. For any such family,

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 $n,d$ be positive parameters, let $q\in[1,\infty]$, and consider testing … against … Assume $dq^3=\omega(n^3)$. The signed triangle test is the signed subgraph-count test based…

Let $n,d$ be positive parameters, let $q\in[1,\infty]$, and consider testing … against … Here the signed four-cycle test is the signed subgraph-count test based on the four-cycle…

Powerlessness conjecture. When $\gamma<\tfrac{1}{2}$, all tests based on the vertex degrees $\{D_v(n)\}_{v\in[n]}$ are powerless, and all tests based on $G_n$ are powerless.

Polynomial-time indistinguishability conjecture. Fix any $c>1$. There exists no polynomial-time algorithm that distinguishes the p-texttt{NPP} from the u-texttt{NPP} with probabili…

Let $\beta \in [-1,\infty)$ and $\gamma>0$. For each $n\in\mathbb N$, set $N=\lceil n/\gamma\rceil$, and let $\mathbb P$ and $\mathbb Q$ be the spiked Wishart distributions defined…

Let $\mathbb{P}_n$ and $\mathbb{Q}_n$ denote a sequence of probability measures with sample space $\mathbb{R}^{n^k}$, where $k=O(1)$. Suppose that every polynomial $f$ of degree…

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…

Simplified exponents-region conjecture. The region $\mathcal{E}^*(R_1,\ldots,R_K,\epsilon_1,\ldots,\epsilon_K)$ is the set of all exponent tuples $(\theta_1,\ldots,\theta_K)$ for w…

Let $(\mathcal{M}_n)_n$ be a family of sets of quantum states satisfying Axioms 1--5 in Section, and let $D^\infty_{\mathcal{M}}(\rho)$ denote the corresponding regularised relativ…

Let $V(n,\pi)$ be the value function defined in, where $n$ denotes the time index, $\pi$ is the relevant state variable, $\mu$ is a prior distribution, and $\nu$ is the parameter a…

Fix constants $\gamma > 0$, $\beta > -1$, and $\rho \in (0,1)$. Let $N=N(n)$ satisfy $n/N \to \gamma$ as $n \to \infty$. In the spiked Wishart model, under $\mathbb{Q}$ the observa…

Planted Affine Planes SoS conjecture. Theorem $$ holds with the bound on the number of sampled vectors loosened to

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…

Extended-test optimality conjecture. If $S_n^{*+}$ satisfies $\bar{l}<\infty$, $v_2>-2$, and $v_l\geq 0$ for all $3\leq l\leq\bar{l}$, then the test is optimal in terms of the gene…