A correct low-degree criterion for polynomial-time hardness of inference
57No. 395 in all physics · No. 6 in Statistical and Nonlinear Physics
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.
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.