A correct low-degree criterion for polynomial-time hardness of inference · revision history
Revision 1
Accepted · first revision · record
- Title
- A correct low-degree criterion for polynomial-time hardness of inference
- Plain
- 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
- 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.
- Settled by
- A theorem establishing a corrected low-degree hardness criterion for a class containing the standard planted problems, or a counterexample within that class.
- Kind
- well-posed
- Answer type
- proof
- References
- (empty)
- Literature status
- contested
- Status 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.
- Posed since
- 2018