Polynomial-time low-degree conjecture

Hopkins formulated the conjecture in 2018: failure of all sufficiently low-degree tests should imply computational indistinguishability in broad permutation-invariant average-case settings. The question is now directly challenged in the graph setting.

Known results

• Holmgren and Wein, 2021: symmetric real-valued counterexample to the original noise formulation, and a Boolean counterexample without permutation invariance.
• Buhai et al., 2025: permutation-invariant examples with quasipolynomial-time distinguishers.
• Jia and Vijayaraghavan, 2026: a polynomial-time test for continuous robust subspace recovery with a nonproduct null.

2026 graph counterexample

For each fixed $r \ge 3$, the preprint constructs permutation-invariant graph distributions whose marginals on $D_n=\Theta((\log n)^{r-1})$ edges are exactly uniform, yet a deterministic polynomial-time rank test distinguishes them after fixed-rate edge resampling. This claims to refute the standard graph conjecture. The construction is nonconstructive; uniformly samplable examples remain open.

Current status (as of July 2026): The graph conjecture has a claimed counterexample with zero low-degree advantage through $D_n=\Theta((\log n)^{r-1})$ and a polynomial-time distinguisher after resampling, but independent verification is not recorded; uniform samplability remains open.