A correct low-degree criterion for polynomial-time hardness of inference
57No. 395 in all physics · No. 6 in Statistical and Nonlinear Physics
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: it names recent work and was partly written without a live literature search; it awaits a check by an editor.
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.
No solutions, ideas or subproblems yet.
See also
- Related Polynomial-time algorithms beating the overlap-gap threshold for independent sets
- Related Sample complexity of gradient training for multi-index targets
Details, signature and history
- Kind
- Well-posed question
- Answer
- Proof
- Posed
- 2018
- Topic review
- L. Zdeborova and F. Krzakala, Statistical physics of inference: thresholds and algorithms, Advances in Physics 65, 2016. Link
- Record
- Revision 1 · imported from the seed collection · compiled by AI, not yet reviewed by an editor
Proof
- Fingerprint
- 20cdba5cac45…
- Public log
- Entry 2,092, in checkpoint 2,123
- In the log by
- Block 969,698, 2026-10-03
This text was in the PubPhys log by that date. The date says nothing about when the problem was first posed.
Comments (0)
Comments are not records: they are not signed, stamped or logged. How comments work
No comments yet.
Sign in to comment.