The Polynomial-Time Low-Degree Conjecture
Statement
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.
Record
Comments
No person has examined this. Nothing here has been checked at all. say whether it holds →
construction · #1
Songtao Mao, using ChatGPT 5.4, 5.5, 5.6That credit came with the record as it was imported. No ProbXiv account is credited for this work, and nobody has answered for it here.
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.
Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.
Sign inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.