Breakthrough Tracker record
A counterexample to the polynomial-time low-degree conjecture
The paper constructs permutation-invariant graph distributions whose low-degree advantage vanishes through polylogarithmic degree, yet a deterministic rank test distinguishes the noisy planted model from the uniform null model in polynomial time.
← Back to the filtered Breakthrough Tracker
- Stable ID
polynomial-time-low-degree-conjecture-counterexample-2026- Revision
polynomial-time-low-degree-conjecture-counterexample-2026.v1- Field
- Computer Science · Average-case complexity and statistics
- Evidence
- Tier 1 · Peer reviewed: No
- Record state
- Provisional · Provisional counterexample
- Last checked
AI role
The author discloses substantial proof assistance from ChatGPT 5.4, 5.5 and 5.6, including development of the rank argument, and states that the proofs were independently checked, simplified and organized by the author.
Record details
- Problem or result
- The standard binary polynomial-time low-degree conjecture after independent noise
- Authors
- Songtao Mao
- Institutions
- Johns Hopkins University
- Result date
- Preprint submitted July 22, 2026
Why it matters
The low-degree method is widely used as evidence of average-case computational hardness. A valid counterexample would identify a missing condition in the standard conjecture.
Limits
This is a first-version preprint without located independent specialist assessment or peer review. The construction refutes the specific formulation stated in the paper; it does not invalidate every low-degree heuristic or lower bound.
Sources
Correction and revision history
- 2026-07-23 — Prepared as a provisional tracker addition with the exact formulation, rank-test mechanism and disclosed AI role stated explicitly.
Machine-readable: JSON v1 · CSV v1 · Schema v1
This individual record remains noindex until a story-specific featured image passes Kingy’s rendered-pixel visual review. The source-linked tracker hub remains the public index.