A correct low-degree criterion for polynomial-time hardness of inference

57

No. 395 in all physics · No. 6 in Statistical and Nonlinear Physics

Non-expert version

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.

How results are checked

See also

Comments (0)

Comments are not records: they are not signed, stamped or logged. How comments work

No comments yet.

Sign in to comment.

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.

History