- The low-degree method is widely used to guide algorithm design and provide evidence of computational hardness, leading to the low-degree conjecture about efficient distinguishability under permutation symmetry and independent noise.
- This paper disproves the polynomial-time low-degree conjecture by constructing a family of permutation-invariant distributions on simple graphs where low-degree advantage is zero through degree D_n, yet a polynomial-time rank test strongly distinguishes them after independent resampling.
- The construction uses a subspace of a Reed–Muller code with low-bias polynomials, selects points without short linear dependencies, and evaluates a random alternating bilinear form, showing that low-degree indistinguishability alone does not imply polynomial-time hardness.