A correct low-degree criterion for polynomial-time hardness of inference
In plain words
A popular test predicts that a hidden signal cannot be found quickly whenever no low-degree polynomial (a simple formula built from products of a few data entries) can detect it. Recent counterexamples show this test fails in some cases, and the task is to find the exact conditions under which it is right.
Precise statement
For a planted distribution $P_n$ and a null distribution $Q_n$ on $\{0,1\}^M$ (for example random graphs), the degree-D advantage is the best correlation of a degree-D polynomial with the likelihood ratio $\mathrm{d}P_n/\mathrm{d}Q_n$. Identify an explicit, checkable condition on $(P_n, Q_n)$ such that a bounded advantage at $D \sim \operatorname{polylog}(n)$, together with the condition, implies that no polynomial-time algorithm distinguishes $P_n$ from $Q_n$ after independent noise; or prove that no condition covering standard planted problems (planted clique, sparse PCA, tensor PCA, community detection) can exist. An answer is a stated corrected conjecture with a proof, or a proof that the program fails.
What would settle it
A theorem establishing a corrected low-degree hardness criterion for a class containing the standard planted problems, or a counterexample within that class.
Status in the literature
Unverified note
Holmgren and Wein (2020) gave counterexamples lacking symmetry, which motivated the permutation-invariance and noise conditions; Buhai, Hsieh, Jain and Kothari (2025, arXiv:2505.17360) refuted the quasi-polynomial version of Hopkins' conjecture, and Mao (July 2026 preprint, arXiv:2607.20318, not yet refereed) reports a counterexample to the polynomial-time version for permutation-invariant graph distributions; both are permutation-invariant and stable under noise, so a valid criterion needs a further condition.