Pith. sign in

REVIEW 1 major objections 3 minor 1 cited by

The paper constructs permutation-invariant graph distributions that are exactly uniform on every small set of edges, so the low-degree advantage is zero, yet a deterministic polynomial-time rank test still distinguishes them from G(n,1/2) a

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

T0 review · deepseek-v4-flash

2026-08-01 10:10 UTC pith:REIZKWB3

load-bearing objection A likely correct disproof of the polynomial-time low-degree conjecture, with the null-side rank analysis resting on a single black-box Reed-Muller theorem that a referee should verify. the 1 major comments →

arxiv 2607.20318 v1 pith:REIZKWB3 submitted 2026-07-22 cs.CC cs.DS

The Polynomial-Time Low-Degree Conjecture is False

Songtao Mao This is my paper
classification cs.CC cs.DS MSC 68Q1794B0560C05
keywords low-degree methodlow-degree conjectureReed–Muller codespermutation invariancestatistical-computational gapsaverage-case hardnesshypothesis testingpolynomial-time algorithms
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper sets out to refute the polynomial-time low-degree conjecture, which says that if a permutation-invariant planted distribution has bounded advantage for low-degree polynomial tests, then no polynomial-time test should strongly distinguish it from the uniform null after fixed-rate independent resampling. The paper constructs, for every fixed r≥3, a permutation-invariant distribution P_n on n-vertex graphs whose every marginal on up to D_n=Θ((log n)^(r-1)) edges is exactly uniform, so the low-degree advantage is exactly zero through that degree. It then exhibits a deterministic polynomial-time rank test that, after a fixed positive resampling rate, strongly distinguishes the noised planted distribution from G(n,1/2). A sympathetic reader should take away that low-degree indistinguishability plus permutation symmetry plus a uniform null plus noise resampling does not by itself force computational hardness; a valid general conjecture must impose some additional condition.

Core claim

The paper claims to disprove Conjecture 1.1, the polynomial-time low-degree conjecture. For every fixed r≥3, it builds a permutation-invariant distribution P_n on simple graphs such that every marginal of P_n on at most D_n=Θ((log n)^(r-1)) edges is exactly uniform; consequently the low-degree advantage Adv_{≤D_n}(P_n,G(n,1/2)) equals 0, not merely O(1). Nevertheless, after each edge is independently resampled at a fixed rate ε_r∈(0,1), a deterministic algorithm running in time n^{C_r} strongly distinguishes T_{ε_r}P_n from G(n,1/2). The construction chooses a subspace of a Reed–Muller code in which every nonzero polynomial has absolute bias at most n^{-3}, selects n evaluation points whose

What carries the argument

The central object is a punctured Reed–Muller construction: a K-dimensional subspace W of the binary Reed–Muller space RM(m,r), with m=Θ(log n) and K=Θ((log n)^r), such that every nonzero polynomial in W has absolute bias at most n^{-3}. Evaluation points are chosen so that their K-bit evaluation vectors have no zero-sum subset of size at most L=Θ((log n)^(r-1)). A uniform alternating bilinear form B on F_2^K is then evaluated on pairs of these vectors, and a uniform vertex permutation is applied; the resulting graph distribution is permutation-invariant and exactly D_n-wise uniform. The distinguisher is a rank test: it fixes T=Θ(log n) anchor vertices, maps each remaining vertex to the T-bi

Load-bearing premise

The proof that the rank test returns 'null' under G(n,1/2) relies wholly on an external theorem stating that a random subset of F_2^T of size at most (1-δ_0) times the Reed–Muller dimension has linearly independent evaluation columns; if that theorem silently requires conditions outside the ranges used here, the null-side analysis would need repair.

What would settle it

Fix the proof's parameters, e.g., take a=3, σ=1, T=⌊a log n⌋, s=⌊σ log n⌋, and for many samples from G(n,1/2) compute the rank of the corresponding R_0×N_0 monomial matrix; the proof asserts full column rank with probability 1-o(1). A single large n with non-negligible rank deficit would falsify the null analysis. Separately, exhibiting a nonzero polynomial in W with absolute bias exceeding n^{-3}, or a subset of at most L evaluation vectors summing to zero, would break the local-uniformity step and the vanishing low-degree advantage.

Watch this falsifier — get emailed when new claim-graph text bears on it.

If this is right

  • The polynomial-time low-degree conjecture, in its standard binary graph form, is false.
  • Exact agreement with the null on every marginal up to degree Θ((log n)^(r-1)) does not preclude polynomial-time strong distinction after a fixed positive resampling rate.
  • The distinguishing algorithm is deterministic, runs in polynomial time n^{C_r}, and has an exactly computable decision threshold, so the counterexample does not rely on randomized or nonuniform computational resources beyond the nonconstructive choice of the planted distribution.
  • The planted distributions are permutation-invariant and exactly D_n-wise uniform, so all low-degree statistics, not just bounded-advantage ones, coincide with G(n,1/2).

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The construction is nonconstructive: the subspace W and evaluation points are produced by the probabilistic method and then fixed, so the refutation does not automatically yield a uniformly samplable hard instance; the paper itself leaves that as an open problem.
  • The null-side analysis rests entirely on a black-box theorem about random puncturings of Reed–Muller codes; if that theorem carries hidden conditions beyond the stated regime, the proof that the test declares 'null' under G(n,1/2) would need repair.
  • The same recipe—a punctured Reed–Muller subspace with small bias plus a random alternating form—could plausibly be adapted to other symmetry groups or to non-graph settings such as hypergraphs or Boolean functions, producing further separations between low-degree statistics and efficient computation.
  • The result suggests that low-degree lower bounds, while often predictive, can miss algebraic structure that survives independent noise; practitioners should treat low-degree indistinguishability as weaker evidence of hardness than the conjecture assumed.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

1 major / 3 minor

Summary. The paper claims to refute the polynomial-time low-degree conjecture (Conjecture 1.1). For every fixed r ≥ 3, it constructs a permutation-invariant distribution P_n on graphs that is exactly D_n-wise uniform for D_n = Θ((log n)^{r-1}) relative to Q_n = G(n,1/2), so that Adv_{≤D_n}(P_n,Q_n)=0. Nevertheless, after independent resampling of every edge at a fixed positive rate ε_r, a deterministic rank test based on anchor-edge vectors and their monomial lift distinguishes T_{ε_r}P_n from Q_n with high probability in time n^{C_r}. The construction uses a subspace of a Reed–Muller code with small bias, a puncturing with no short linear dependencies among evaluation vectors, and a random alternating bilinear form. The proof also gives a nonuniform sampler for P_n. If correct, this is a counterexample to the conjecture in its standard binary, polynomial-time formulation.

Significance. This is a significant result. It shows that exact low-degree agreement, permutation invariance, and a uniform null distribution do not by themselves imply computational hardness after resampling, contrary to a widely used heuristic. The construction is non-obvious: the subspace with small bias (Lemma 2.2), the girth condition on evaluation vectors (Lemma 2.4), and the rank-test distinguisher are elegantly combined, with all constants chosen through explicit inequalities (Lemma 3.5). The paper is honest about its limitations: the planted distribution is nonconstructive, the parameter trade-off depends on r, and a uniformly samplable example remains open. The proof is largely self-contained except for two external Reed–Muller theorems; the distinguisher is a simple explicit algorithm and the runtime analysis is clean.

major comments (1)
  1. [§3.2, Lemmas 3.1 and 3.3] Lemma 3.1 ([BHSS22]) is the sole load-bearing ingredient in the null-side analysis: Lemma 3.3 requires that a uniformly random subset of F2^T of size exactly floor(R0/2) has linearly independent evaluation vectors, with δ0=1/2, s/T → σ/a < γ0, over F2. The paper quotes this as 'Theorem 1.1 and Corollary 4.1' but gives no proof or verification of the exact parameter regime. Since Theorem 1.2 is a disproof of a named conjecture, I ask that the author either reproduce the relevant statement of BHSS22 with all conditions and confirm it includes δ0=1/2 and subset size exactly floor(R0/2), or provide a proof of the needed special case. If the original theorem has hidden restrictions (e.g., δ0 bounded away from 1/2, or only approximate rank independence), the proof of full rank under Q_n would need repair. This is the only non-self-contained step I could identify.
minor comments (3)
  1. [§2.1, Lemma 2.4] The union-bound step writes '(1+η)^n − 1'; the bound e^{nη} − 1 = O(n^{-1}) is standard, but one clarifying sentence would help readers.
  2. [§3.2, Lemma 3.3] The proof jumps from 'the columns indexed by Z are linearly independent' to 'the original columns are therefore independent' without explicitly noting that, in the coupling, U is a subset of Z. This is clear from the construction but could be stated softly.
  3. [§3.4, Lemma 3.5] The constants σ, a, ε are chosen rational, but the floors in T and s introduce o(1) deviations. Since all inequalities are strict, this is harmless, but the proof might mention that the inequalities remain satisfied for sufficiently large n.

Circularity Check

0 steps flagged

No significant circularity: the construction and distinguisher are self-contained and rely on independent external Reed–Muller lemmas, not on fitted parameters or self-citations.

full rationale

The derivation chain is independent: the planted distribution is built from an averaged subspace of RM(m,r) with small bias (Lemmas 2.1–2.2), probabilistically chosen evaluation points with no short dependencies (Lemma 2.4), and a random alternating form. Proposition 2.6 derives D⋆-wise uniformity from linear independence plus surjectivity of the restriction map, and Corollary 2.7 then gives Adv=0 by the definition of the low-degree advantage—this is a consequence, not an input. The distinguisher uses the external BHSS22 puncturing theorem (Lemma 3.1) for the null-side full rank and an internal Reed–Muller dimension bound for the planted-side deficit; Lemma 3.5 chooses constants satisfying the stated hypotheses, with no parameter fitted to make a prediction come out. The only self-citation [Mao26] is a background reference on k-XOR algorithms and does not enter the proof; [BLRS26] is by a different group and is used only in a remark. The paper's stated limitations (nonconstructive choice of W and evaluation points, open explicit/samplable example, reliance on the unproved black-box Lemma 3.1) are correctness/verification risks, not circularity: the black-box lemmas are external theorems independent of the low-degree conjecture, and the union-bound/parameter-regime questions would affect soundness, not self-reference. The AI-assistance statement does not import any argument into the proof.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The counterexample rests on two external Reed-Muller theorems plus standard probabilistic-method and Fourier arguments. The proof constants (b, κ, σ, a, ε) are existential choices satisfying inequalities (Lemma 3.5), not parameters fitted to data; they are not free parameters in the empirical sense. No new postulated entities are introduced.

axioms (2)
  • standard math Lemma 2.1 from Ben-Eliezer-Hod-Lovett [BEHL12]: for m large and r ≤ m/2, a uniform polynomial f ∈ RM(m,r) has |bias(f)| > 2^{-β1 m/r} with probability at most 2^{-β2 C(m,≤r)}.
    Used in Lemma 2.2 to show existence of a K-dimensional subspace of RM(m,r) all of whose nonzero elements have bias ≤ n^{-3}; this is the foundation of the construction.
  • standard math Lemma 3.1 from Bhandari et al. [BHSS22]: for T→∞, s→∞ with s < γ0 T, a uniformly random subset Z ⊆ F_2^T of size ⌊(1-δ_0) C(T,≤s)⌋ has linearly independent Reed-Muller evaluation vectors with probability 1-o(1).
    Used in Lemma 3.3 to prove the rank test has full column rank under the null distribution; without this, the test's false-positive control fails.

pith-pipeline@v1.3.0-alltime-deepseek · 13258 in / 28795 out tokens · 218149 ms · 2026-08-01T10:10:50.427679+00:00 · methodology

0 comments
read the original abstract

The low-degree method and its associated lower bounds are widely used to guide algorithm design and to provide evidence of computational hardness in average-case inference, high-dimensional statistics, random optimization, and related problems. This led to the low-degree conjecture, which predicts that when the low-degree advantage between a planted distribution and a uniform null distribution remains bounded, no efficient distinguisher can succeed after independent noise, provided that the planted distribution has permutation symmetry. Several works have produced counterexamples to variants of this conjecture or to versions for algorithms with higher time complexity, but the conjecture remained open in its standard binary, polynomial-time formulation. We disprove the polynomial-time low-degree conjecture by giving a family of examples in this setting. For every fixed integer $r\geq3$, we construct a permutation-invariant distribution $\mathbb{P}_n$ on simple graphs, with $\mathbb{Q}_n=G(n,1/2)$, such that every marginal of $\mathbb{P}_n$ on at most $D_n=\Theta((\log n)^{r-1})$ edges is uniform. Therefore, the low-degree advantage is zero through degree $D_n$. Nevertheless, after every edge is independently resampled at a fixed positive rate, a deterministic rank test strongly distinguishes the resulting distribution from $\mathbb{Q}_n$ in polynomial time. The construction chooses a subspace of a Reed--Muller code whose nonzero polynomials have small absolute bias, selects points whose evaluation vectors have no short linear dependencies, and evaluates a random alternating bilinear form on pairs of these vectors. Our result shows that low-degree indistinguishability, a uniform null distribution, permutation invariance, and independent resampling do not by themselves imply polynomial-time hardness, and suggests that a valid general conjecture must impose an additional condition.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. The Kikuchi Hierarchy is Sharp for $k$XOR

    cs.DS 2026-07 conditional novelty 8.0

    Normalized Kikuchi matrices achieve the sharp m ~ rho^{-2} n^{k/2} / ell^{k/2-1} trade-off with no logarithmic loss for detection, recovery, and two-sided refutation in kXOR, with matching low-degree lower bounds.

Reference graph

Works this paper leans on

33 extracted references · 1 canonical work pages · cited by 1 Pith paper · 1 internal anchor

  1. [1]

    Computational Complexity , volume =

    Ido Ben-Eliezer and Rani Hod and Shachar Lovett , title =. Computational Complexity , volume =. 2012 , doi =

    2012

  2. [2]

    37th Computational Complexity Conference (CCC 2022) , series =

    Siddharth Bhandari and Prahladh Harsha and Ramprasad Saptharishi and Srikanth Srinivasan , title =. 37th Computational Complexity Conference (CCC 2022) , series =. 2022 , doi =

    2022

  3. [3]

    Kothari , title =

    Rares-Darius Buhai and Jun-Ting Hsieh and Aayush Jain and Pravesh K. Kothari , title =. 2025. 2025 , doi =

    2025

  4. [4]

    Hopkins , title =

    Samuel B. Hopkins , title =. 2018 , doi =

    2018

  5. [5]

    Wein , title =

    Justin Holmgren and Alexander S. Wein , title =. 12th Innovations in Theoretical Computer Science Conference (ITCS 2021) , series =. 2021 , doi =

    2021

  6. [6]

    Wein and Afonso S

    Dmitriy Kunisky and Alexander S. Wein and Afonso S. Bandeira , title =. Mathematical Analysis, Its Applications and Computation , series =. 2022 , doi =

    2022

  7. [7]

    Wein , title =

    Alexander S. Wein , title =. 2025 , eprint =. doi:10.48550/arXiv.2506.10748 , note =

    Pith/arXiv arXiv doi:10.48550/arxiv.2506.10748 2025

  8. [8]

    Hopkins and Jonathan A

    Boaz Barak and Samuel B. Hopkins and Jonathan A. Kelner and Pravesh K. Kothari and Ankur Moitra and Aaron Potechin , title =. SIAM Journal on Computing , volume =. 2019 , doi =

    2019

  9. [9]

    Hopkins and Pravesh K

    Samuel B. Hopkins and Pravesh K. Kothari and Aaron Potechin and Prasad Raghavendra and Tselil Schramm and David Steurer , title =. 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS) , pages =. 2017 , doi =

    2017

  10. [10]

    Hopkins and David Steurer , title =

    Samuel B. Hopkins and David Steurer , title =. 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS) , pages =. 2017 , doi =

    2017

  11. [11]

    Bandeira and Jess Banks and Dmitriy Kunisky and Christopher Moore and Alexander S

    Afonso S. Bandeira and Jess Banks and Dmitriy Kunisky and Christopher Moore and Alexander S. Wein , title =. Proceedings of the Thirty-Fourth Conference on Learning Theory , series =. 2021 , url =

    2021

  12. [12]

    Bandeira and Dmitriy Kunisky and Alexander S

    Afonso S. Bandeira and Dmitriy Kunisky and Alexander S. Wein , title =. 11th Innovations in Theoretical Computer Science Conference (ITCS 2020) , series =. 2020 , doi =

    2020

  13. [13]

    Wein and Afonso S

    Yunzi Ding and Dmitriy Kunisky and Alexander S. Wein and Afonso S. Bandeira , title =. IEEE Transactions on Information Theory , volume =. 2021 , doi =

    2021

  14. [14]

    Wein and Afonso S

    Yunzi Ding and Dmitriy Kunisky and Alexander S. Wein and Afonso S. Bandeira , title =. Foundations of Computational Mathematics , volume =. 2024 , doi =

    2024

  15. [15]

    The Annals of Statistics , volume =

    Jian Ding and Hang Du and Zhangsong Li , title =. The Annals of Statistics , volume =. 2025 , doi =

    2025

  16. [16]

    Wein , title =

    Tselil Schramm and Alexander S. Wein , title =. The Annals of Statistics , volume =. 2022 , doi =

    2022

  17. [17]

    2026 , eprint =

    Songtao Mao , title =. 2026 , eprint =. doi:10.48550/arXiv.2604.10457 , note =

    Pith/arXiv arXiv doi:10.48550/arxiv.2604.10457 2026

  18. [18]

    Brennan and Guy Bresler and Samuel B

    Matthew S. Brennan and Guy Bresler and Samuel B. Hopkins and Jerry Li and Tselil Schramm , title =. Proceedings of the Thirty-Fourth Conference on Learning Theory , series =. 2021 , url =

    2021

  19. [19]

    Wein , title =

    Andrea Montanari and Alexander S. Wein , title =. Probability Theory and Related Fields , volume =. 2025 , doi =

    2025

  20. [20]

    Advances in Neural Information Processing Systems , volume =

    Davin Choo and Tommaso d'Orsi , title =. Advances in Neural Information Processing Systems , volume =. 2021 , url =

    2021

  21. [21]

    2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS) , pages =

    Guy Bresler and Brice Huang , title =. 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS) , pages =. 2022 , eprint =

    2021

  22. [22]

    Wein , title =

    David Gamarnik and Aukosh Jagannath and Alexander S. Wein , title =. SIAM Journal on Computing , volume =. 2024 , doi =

    2024

  23. [23]

    Kothari and Alon Rosen , title =

    Andrej Bogdanov and Pravesh K. Kothari and Alon Rosen , title =. Theory of Cryptography , series =. 2023 , doi =

    2023

  24. [24]

    Proceedings of the Thirty-Ninth Conference on Learning Theory , series =

    He Jia and Aravindan Vijayaraghavan , title =. Proceedings of the Thirty-Ninth Conference on Learning Theory , series =. 2026 , url =

    2026

  25. [25]

    Expanders Meet Reed-Muller: Easy Instances of Noisy k-XOR

    Jaros. Expanders Meet. 2026 , eprint =. doi:10.48550/arXiv.2604.04188 , note =

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.48550/arxiv.2604.04188 2026

  26. [26]

    The Annals of Statistics , volume =

    Guanyi Chen and Jian Ding and Shuyang Gong and Zhangsong Li , title =. The Annals of Statistics , volume =. 2026 , doi =

    2026

  27. [27]

    Wein , title =

    Abhishek Dhawan and Cheng Mao and Alexander S. Wein , title =. Random Structures & Algorithms , volume =. 2025 , doi =

    2025

  28. [28]

    2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS) , pages =

    Dmitriy Kunisky and Xifan Yu , title =. 2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS) , pages =. 2024 , doi =

    2024

  29. [29]

    Wein , title =

    Cheng Mao and Alexander S. Wein , title =. Bernoulli , volume =. 2025 , doi =

    2025

  30. [30]

    2025 , eprint =

    Zhangsong Li , title =. 2025 , eprint =. doi:10.48550/arXiv.2511.06040 , note =

    doi:10.48550/arxiv.2511.06040 2025

  31. [31]

    Bandeira and Ahmed El Alaoui and Samuel B

    Afonso S. Bandeira and Ahmed El Alaoui and Samuel B. Hopkins and Tselil Schramm and Alexander S. Wein and Ilias Zadik , title =. Advances in Neural Information Processing Systems , volume =. 2022 , url =

    2022

  32. [32]

    Wein , title =

    Alexander S. Wein , title =. Mathematical Statistics and Learning , volume =. 2021 , doi =

    2021

  33. [33]

    Kane and Pravesh K

    Jun-Ting Hsieh and Daniel M. Kane and Pravesh K. Kothari and Jerry Li and Sidhanth Mohanty and Stefan Tiegel , title =. Proceedings of the 58th Annual ACM Symposium on Theory of Computing , pages =. 2026 , doi =

    2026