Lyu et al.'s low-degree hardness conjecture for shared-subspace detection

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 $\bm{A}^{(l)}\sim\bm{S}^{(l)}+\bm{N}^{(l)}$ for all $l$, where

$$\bm{S}^{(l)}=\varepsilon_l\lambda\bm{u}\bm{u}^{\top},\qquad \varepsilon_l\sim\operatorname{IID\ Rademacher},$$

and $\bm{u}$ has entries independently and uniformly in $\{\pm n^{-1/2}\}$. Denote $\bm{X}=\{\bm{A}^{(l)}\}_{l=1}^L$, and let $L_n^{\leq D}(\bm{X})$ be the degree-$D$ projection of the likelihood ratio from $\mathbb{P}_n$ to $\mathbb{Q}_n$. Lyu et al.'s low-degree hardness conjecture. If there exist $\varepsilon\geq0$ and $D\geq\log(nL)^{1+\varepsilon}$ such that $\|L_n^{\leq D}(\bm{X})\|^2=1+o(1)$, then no polynomial-time test $\phi_n:\mathbb{R}^{L\times n\times n}\mapsto\{0,1\}$ has

$$\mathbb{E}_{\mathbb{Q}_n}[\phi_n(\bm{X})]+\mathbb{E}_{\mathbb{P}_n}[1-\phi_n(\bm{X})]\to0$$

as $n\to\infty$. This is a computational-statistical conjecture for detecting a shared rank-one subspace under randomized signs; the paper uses it as evidence for the necessity of its computational signal-to-noise condition, and the claim remains open.