The Polynomial-Time Low-Degree Conjecture
The low-degree conjecture predicts that when the low-degree advantage between a planted distribution and a uniform null distribution stays bounded, no polynomial-time algorithm can distinguish them. It is false. There is a planted distribution that agrees with the null through the relevant degree, is invariant under vertex relabeling, and is nevertheless distinguished in polynomial time by a rank argument.
- Result
- Disproved(see note)
- Status
- Resolved
- AI contribution
- AI co-developed
- Method
- Construction
- Field
- Average-case complexity
- Posed by
- Samuel B. Hopkins
- Year posed
- 2018
- Years open
- 8y
- Solved
- 2026-07-22
- Model
- ChatGPT 5.4, 5.5, 5.6
- Vendor
- OpenAI
- Collaborators
- Songtao Mao
- Verification
- Unreviewed
- Publication
- Preprint
- Significance
- 30 / 100
- Disclosed cost
- —
- Wikipedia
- No dedicated article
What was actually shown
the construction is probabilistic; an explicit uniformly samplable example remains open
What the AI did
The statement on AI use is specific in both directions. The author first put forward constructions from two-dimensional Reed-Muller-style codes and asked whether they could be made invariant under all vertex relabelings while keeping efficient decoding; the model's responses established that they could not, closing off that route. The rank argument that carries the paper was later developed with ChatGPT 5.6 after the author fed it ideas in the spirit of his Remark 2.5. The author independently checked, simplified and organized every proof.
Verification
Single-author arXiv preprint; not yet peer-reviewed.
Source
arXiv:2607.20318 - The Polynomial-Time Low-Degree Conjecture is False