{"id":"75f1c3a9-9617-4801-8e62-6a74a0c3e289","arxiv_id":"2505.00974","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"The paper proves that the Gibbs decoder for Reed-Muller codes can have super-polynomial mixing time on certain typical received sequences, so it is not a worst-case polynomial-time decoder.","lead":"This paper analyzes the Gibbs decoder, a Markov chain based method for decoding Reed-Muller codes, and proves that for some carefully chosen channel outputs it can take super-polynomial time to converge. The result is a worst-case negative result for a natural candidate decoder, leaving average-case performance and other MCMC decoders as open questions.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 3's uniform bound is not established: the final asymptotic step drops the rate-dependent coefficient c=Φ^{-1}(R), so for small p and R near capacity the proven lower bound is exponentially weaker than claimed; the R=0 case is a concrete counterexample.","rationale":"The reader correctly identified the R=0 boundary problem and the unquantified normal approximation. My pass found a more serious gap in the same asymptotic step: c=Φ^{-1}(R) is dropped when converting Lemma 4's δ_i into the final mixing-time bound. For p small and R close to 1-H(p), the omitted factor 2^{-(c/2)√m} is not absorbed by the claimed exp(-√log n) term; the actual lower bound can be exponentially weaker than the displayed Ω(exp(√n·exp(-√log n))). This affects a continuum of interior rates, not just the R=0 boundary, so the theorem as stated is not proven. The superpolynomial conclusion itself is plausibly salvageable, since even the corrected lower bound gives Tmix=exp(n^{1/2-o(1)}), which is still superpolynomial. I therefore keep the reader's CONDITIONAL disposition rather than escalating to REJECT: the core insight appears sound, but the theorem statement and final derivation need revision. My agreement is partial because the reader emphasized the R=0 boundary and approximation error, whereas the dropped c coefficient is the more structurally important defect; both should be addressed in revision.","tokens_in":9769,"tokens_out":13870,"duration_ms":129912,"concrete_test":"Re-derive the last line of Theorem 3 without dropping c=Φ^{-1}(R): from Lemma 4's δ_i ≥ 2^{m-r-q+1} and r=m/2+c√m/2+o(√m), compute log Tmix ≥ √n·2^{-(c/2)√m}·2^{1-q} and compare this with the claimed √n·2^{-√m/√ln2} up to constants. For p=10^{-4} and R=0.998 (c≈2.88, q=14), the ratio is 2^{-(c/2-1/√ln2)√m}→0, so the claimed Ω does not follow; repeat the same computation for c=0 (R=0.5) to confirm that the claimed bound is only valid in the regime c≤2/√ln2. Separately, test R=0 with r_j=0: the chain has two states and constant mixing time, contradicting the theorem as stated.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim is the uniform lower bound in Theorem 3. Lemma 4 only yields δ_i ≥ 2^{m-r-q+1}, where q=⌈log_2(1/p)⌉. The proof of Theorem 3 then substitutes the normal approximation r = m/2 + c√m/2 with c=Φ^{-1}(R) and immediately concludes Tmix = Ω(exp(√n·exp(-√log n))), silently dropping both c and q. Writing L=ln n = m ln2, Lemma 3 plus Lemma 4 give log Tmix ≥ 2^{m-r-q+1} ≈ 2^{m/2 - (c/2)√m - q} = √n · exp(-(c√ln2/2)√L - q ln2). The claimed bound requires log Tmix ≥ c' √n · exp(-√L), which holds only if c√ln2/2 ≤ 1, i.e. c ≤ 2/√ln2 ≈ 2.401. This condition fails for valid parameters: with p=10^{-4}, H(p)≈1.47×10^{-3}, so the theorem allows R<0.9985; taking R=0.998 gives c=Φ^{-1}(R)≈2.88 and c√ln2/2≈1.20>1. Then the actual lower bound is exp(√n·e^{-1.20√log n}), which is not Ω(exp(√n·e^{-√log n})) because the ratio of the exponents tends to 0. Thus the proof does not establish the theorem on a non-trivial parameter region, and a corrected statement must either carry the rate-dependent exponent or weaken the bound to exp(n^{1/2-o(1)}). Additionally, the theorem literally includes R=0: for RM(0,m), the code has two messages, k=1, and the Gibbs chain has constant mixing time, so the stated lower bound is false there. Both issues are fixable — restrict to R>0 and state the bound with the explicit c dependence — but as written the central theorem is not proven.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"This paper studies the mixing time of the Gibbs decoder (Glauber dynamics on the message space) for Reed–Muller codes over the binary symmetric channel. The main result, Theorem 3, claims that for any crossover probability p < 1/2 and any asymptotic rate R < 1 - H(p), there exists a sequence of conditionally typical received sequences for which the mixing time of the Gibbs decoder is Ω(exp(√n · exp(−√log n))), i.e., super-polynomial. The proof combines a conductance-based bottleneck lemma (Lemma 3) with an explicit construction of a received vector y (Lemma 4) such that the all-zero message has posterior mass at most 1/2 and every single-bit flip increases the Hamming distance to y by at least 2^{m−r−q+1}, where q = ⌈log_2(1/p)⌉. The final asymptotic step converts r ≈ m/2 + c√m/2 into a lower bound on the mixing time using the normal approximation to the binomial distribution.","tokens_in":10116,"tokens_out":16095,"duration_ms":147996,"significance":"If the main theorem were correct as stated, it would be a notable worst-case lower bound: it would show that a natural MCMC decoder for RM codes can require super-polynomial time to converge to the posterior, in contrast to the capacity-achieving MAP decoding of RM codes. The construction in Lemma 4 is explicit and the conductance argument is self-contained. However, as written the theorem is not proven: the proof drops a rate-dependent exponent, and the statement is false for R = 0. The qualitative super-polynomial conclusion appears salvageable after restricting the rate range and carrying the rate-dependent constants, but the paper in its current form does not establish the stated uniform bound.","major_comments":[{"comment":"The passage from the bound δ_i ≥ 2^{m−r−q+1} to the claimed log T_mix = Ω(√n exp(−√log n)) silently drops the dependence on c = Φ^{-1}(R). Substituting r = m/2 + (c/2)√m into the Lemmas 3–4 lower bound gives log T_mix = Ω(2^{m/2 − (c/2)√m − q + 1}) = Ω(√n · 2^{−q+1} · exp(−(c√ln 2 / 2)√log n)). The claimed uniform bound holds only when c√ln 2 / 2 ≤ 1, i.e., R ≤ Φ(2/√ln 2) ≈ 0.9918. For p small enough that 1 − H(p) > 0.9918, the theorem's assumptions allow rates in (0.9918, 1 − H(p)) for which the proven bound is exp(√n · exp(−C√log n)) with C > 1, which is not Ω(exp(√n · exp(−√log n))) because the ratio of the exponents tends to zero. Please either restrict the theorem to the regime c√ln 2 / 2 ≤ 1 or state the rate-dependent bound; the latter still yields the advertised super-polynomiality for every fixed R < 1 − H(p).","section":"Theorem 3, proof"},{"comment":"The theorem claims any rate R < 1 − H(p), which includes R = 0. For the sequence RM(0,m) (r = 0, k = 1), the message space has two states and the Gibbs chain has P(0→1) = µ(1), P(1→0) = µ(0); after one step the distribution is exactly the stationary distribution, so T_mix = 1, contradicting the claimed lower bound. The proof fails at Lemma 4(2): the codeword c = Eval(z_m + 1) used for the comparison message u is not in RM(0,m), so the posterior comparison µ(u) ≥ µ(0) is unavailable; indeed µ(0) > 1/2 in that case. The theorem and Lemma 4 must exclude r = 0 (or state a separate treatment).","section":"Theorem 3 (statement), Lemma 4"},{"comment":"Equation (2) treats the normal approximation to the binomial CDF as an exact identity and inverts it to obtain r = m/2 + (c/2)√m. The paper does not quantify the approximation error. Since the exponent of the mixing-time lower bound depends on r through √n · 2^{−r}, an unquantified O(1) error in r would change the constant in front of √log n, so the asymptotic conclusion is not rigorous as written. A Berry–Esseen bound (or a direct large-deviation estimate) should be invoked to justify the expansion for the fixed-rate sequences under consideration.","section":"§IV, Eq. (2)"}],"minor_comments":[{"comment":"The statement says \"there exists a non-zero vector y ∈ F_m^2\"; this should read y ∈ F_2^{2^m} (or F_2^n).","section":"Lemma 4 statement"},{"comment":"The notation \"d/(2q−1)\" is missing an exponent; it should be d/2^{q−1}.","section":"Lemma 4 statement (3)"},{"comment":"The bound is written as δ_i ≥ 2^{m−r−q}, whereas Lemma 4 gives 2^{m−r−q+1}; the exponent is off by one. This does not change the asymptotics but should be corrected.","section":"Theorem 3 proof"},{"comment":"The formula \"k = (m ≤ r)\" in the proof of Theorem 3 is typeset incorrectly; it should be the binomial sum ∑_{i=0}^r \\binom{m}{i}.","section":"Theorem 3 proof"}],"recommendation":"major_revision","confidential_remarks":"The main theorem's quantitative bound is not established for all stated parameter regimes, and the R = 0 case is a counterexample to the statement as written. The underlying construction appears sound for R > 0 and rates away from capacity, so I believe the paper is salvageable with a revised theorem statement. However, the revision should also address the normal-approximation rigor gap."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: this paper has a real result—an explicit typical received sequence that makes the Gibbs decoder on RM codes mix super-polynomially slowly in the worst case—and the construction is clean. But the headline theorem states a stronger uniform bound than the proof supports, and it literally includes R=0 where the statement is false. The fix is straightforward, so I'd send it to review.\n\nWhat's new: the bottleneck construction itself. Lemma 4 gives a y whose distance to every generator row increases by at least 2^{m-r-q+1}, so the all-zero message is a trap. That's a concrete adversarial input for every RM code, not a heuristic. Lemma 3 is just conductance in a singleton set, which is standard, but the combination is effective. The paper is also honest about scope: worst-case only, average-case remains open, and they mention annealed/block variants that might escape the bound. Citations look appropriate; the Liu-Cuff-Verdú lemma is only motivation, and the proof relies on standard conductance theorems.\n\nWhere it slips: the proof of Theorem 3 silently drops the rate-dependent coefficient c=Φ^{-1}(R) and the q from Lemma 4. Chasing the constants gives log T_mix = Ω(√n exp(-(c ln2/2)√log n)) (up to p-dependent factors), not the claimed exp(-√log n) unless c≤2/√ln2. For p=10^{-4} and R=0.998, c≈2.88 and the exponent constant is about 1.2, so the proven bound is strictly weaker. That's a repairable gap, and the qualitative super-polynomiality survives for every fixed R<1-H(p), since √n exp(-a√log n) is super-polynomial for any fixed a.\n\nThe R=0 boundary is a real counterexample to the theorem as stated: RM(0,m) has two messages and constant mixing time. The theorem needs R>0 (or r_j→∞), and the last asymptotic step should carry the c-dependence or state the weaker exp(n^{1/2-o(1)}) form.\n\nThe normal approximation in Eq. (2) is also invoked without a Berry-Esseen error term, and Lemma 3's constant handling is loose. Both are minor and standard to fix.\n\nBottom line: the central claim—worst-case super-polynomial mixing for Gibbs decoding of RM codes—is credible and new. The exact uniform asymptotic in Theorem 3 is not established as written. A careful referee would ask for the rate-dependent statement and the R=0 exclusion. This deserves peer review, not a desk reject.","headline":"A genuine worst-case slow-mixing result for Gibbs decoding of RM codes, but Theorem 3 as stated overclaims; the core bound survives with rate-dependent constants.","tokens_in":10728,"tokens_out":3899,"would_cite":true,"duration_ms":37626,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["94B35","60J10"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper establishes that the Gibbs decoder has super-polynomial worst-case mixing time for Reed–Muller codes over the binary symmetric channel.","keywords":["Reed–Muller codes","Gibbs decoder","mixing time","Markov chain Monte Carlo","posterior sampling","bottleneck ratio","binary symmetric channel","super-polynomial complexity"],"falsifier":"Take the sequence $RM(0,m)$ with any $p<1/2$: the message space has only two states, the Gibbs transition matrix is $2\\times 2$, and direct diagonalization gives $T_{\\rm mix}=O(1)$ independent of $m$, contradicting the claimed super-polynomial lower bound. This pins the missing hypothesis as $R>0$ (equivalently $r\\ge 1$).","tokens_in":9472,"feed_emoji":"⏳","tokens_out":12061,"duration_ms":112281,"temperature":0.7,"pith_summary":"This paper tries to establish a negative worst-case complexity result for a natural Markov-chain decoder. It shows that for Reed–Muller codes over a binary symmetric channel, the Gibbs decoder can require super-polynomial time to converge to the posterior distribution, even when the received word is conditionally typical for some codeword. The obstruction is a carefully chosen received sequence that makes the all-zero message a bottleneck: the message has moderate posterior probability, but every single-bit flip sharply increases its Hamming distance to the received word, so the sampler is very unlikely to escape. This matters because posterior sampling is known to achieve capacity for Reed-Muller codes, but a decoder that mixes too slowly cannot realize that performance in the worst case. The result leaves open whether average-case mixing or modified Gibbs variants are fast.","feed_headline":"Gibbs decoding can take super-polynomial time on Reed–Muller codes","feed_subtitle":"A specially built received word traps the sampler at the all-zero message, so posterior convergence stalls.","key_machinery":"The proof is carried by two mechanisms. The Gibbs chain on the message space has stationary distribution $\\mu(m)\\propto \\theta^{d_H(mG,y)}$ with $\\theta=p/(1-p)<1$, so posterior mass is exponentially concentrated near codewords close to $y$; a step flips one uniformly chosen message bit with probability $\\mu(m\\oplus i)/(\\mu(m)+\\mu(m\\oplus i))$. The bottleneck ratio (conductance) of a set $S$ is $\\Phi(S)=\\sum_{s_1\\in S,s_2\\notin S}\\mu(s_1)P(s_1\\to s_2)/\\mu(S)$, and the standard bound $T_{\\rm mix}\\ge 1/(4\\Phi(P))$ lets the proof use the single state $S=\\{0\\}$: its conductance is just $1-P(0\\to 0)\\le (1/k)\\sum_i \\theta^{\\delta_i}$, where $\\delta_i=d_H(e_iG,y)-d_H(0,y)$. The constructed polynomial $f_y$ makes $\\delta_i\\ge 2^{m-r-q+1}$ for every generator row, and the normal approximation to the binomial distribution converts the rate condition $R_j\\to R$ into $r=m/2+c\\sqrt{m}/2$, which turns $2^{m-r-q}$ into $\\sqrt{n}\\,\\exp(-\\sqrt{\\log n})$ and hence, through the bottleneck lemma, into the mixing-time lower bound $\\exp(\\Omega(\\sqrt{n}\\,\\exp(-\\sqrt{\\log n})))$.","core_discovery":"The central claim is that, for any crossover probability $p<1/2$ and any rate $R<1-H(p)$, every sequence of Reed–Muller codes with unbounded length and rate approaching $R$ admits received words for which the Gibbs decoder mixes in time $\\Omega(\\exp(\\sqrt{n}\\cdot \\exp(-\\sqrt{\\log n})))$, which is super-polynomial in the blocklength $n=2^m$. The proof constructs the received word as the evaluation of the polynomial $f_y(z_1,\\dots,z_m)=(\\prod_{i=1}^{q-1}z_i+1)(z_m+1)$ with $q=\\lceil\\log_2(1/p)\\rceil$. For this word, the all-zero message has posterior probability at most $1/2$, while flipping any one message bit changes the Hamming distance to $y$ by at least $2^{m-r-q+1}$; the Gibbs chain must cross this exponentially small escape probability, and the bottleneck-ratio bound converts it into the super-polynomial mixing-time lower bound. In the paper's own terms, this is a worst-case lower bound on the complexity of Gibbs decoding, not a statement about average received words.","pith_inferences":["The bottleneck construction is likely not special to Reed–Muller structure: any linear code whose generator rows have weights growing like $2^{m-r}$ and that contains a codeword at distance $2^{m-q}$ from a suitable received word would yield the same lower bound through the same bottleneck argument.","A direct check at rate zero shows the theorem needs an $R>0$ (or $r\\ge 1$) hypothesis; replacing the normal approximation with an exact binomial tail bound would make the statement airtight for positive rates and quantify the constant in the exponent.","Empirically, the bound may be loose: running the Gibbs chain on the constructed received word at moderate blocklengths would show whether the bottleneck at the all-zero message is as severe as the exponent suggests, and whether annealed or block-update variants escape it.","If average-case mixing were later shown to be polynomial, then combining that with the posterior-sampling equivalence lemma would produce a polynomial-time capacity-achieving posterior-sampling decoder for Reed–Muller codes; the present worst-case result would not contradict it."],"forward_implications":["For every $p<1/2$ and every rate below capacity, some conditionally typical received word makes the Gibbs chain take $\\Omega(\\exp(\\sqrt{n}\\,\\exp(-\\sqrt{\\log n})))$ steps to mix, so no universal polynomial worst-case guarantee is possible for this decoder.","The bad received words are not arbitrary adversarial noise; each lies in the conditional typical set for a codeword, so the slow mixing can occur on outputs the channel would actually produce.","Because the only property used is an energy gap under single-bit flips, any MCMC decoder whose updates resample one message bit from the posterior will inherit the same exponential mixing lower bound for the same constructed words.","The result does not settle average-case complexity: the constructed received word may have vanishing probability, and the paper explicitly leaves open the possibility that typical received sequences mix quickly on average."],"supporting_citations":[{"why":"Supplies the lemma that posterior sampling's error probability is within a factor of two of MAP, which is why sampling-based decoders are worth analyzing.","marker":"[12]"},{"why":"Provides the ergodicity criterion and the bottleneck-ratio lower bound $T_{\\rm mix}\\ge 1/(4\\Phi(P))$ used to convert the small escape probability into a mixing-time lower bound.","marker":"[16]"},{"why":"Establishes vanishing bit-error probability for Reed–Muller codes under MAP on binary memoryless symmetric channels, the baseline a fast decoder would need to match.","marker":"[4]"},{"why":"Completes the capacity-achieving premise for Reed–Muller codes under MAP by establishing vanishing block-error probability on symmetric channels.","marker":"[5]"}],"fun_headline_variants":["Gibbs decoding worst-case is super-polynomial for RM codes","RM codes: Gibbs decoder worst-case is super-polynomial mixing","Super-polynomial time: Gibbs decoding worst-case on RM codes","Gibbs decoder can stall in super-polynomial time for RM codes","Worst-case Gibbs decoding for RM codes is super-polynomial"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The proof assumes the normal approximation that turns the code rate $R$ into the code order $r$ is accurate enough, without quantifying the error, and the approximation fails at $R=0$, where the stated theorem would be false; the claim therefore implicitly requires $R>0$ (or $r\\ge 1$).","fun_headline_variants_meta":{"raw":{"variants":["Gibbs decoding worst-case is super-polynomial for RM codes","RM codes: Gibbs decoder worst-case is super-polynomial mixing","Super-polynomial time: Gibbs decoding worst-case on RM codes","Gibbs decoder can stall in super-polynomial time for RM codes","Worst-case Gibbs decoding for RM codes is super-polynomial"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000606,"raw_usage":{"total_tokens":2832,"prompt_tokens":962,"completion_tokens":1870,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":578,"completion_tokens_details":{"reasoning_tokens":1783}},"tokens_in":578,"tokens_out":1870,"duration_ms":12939,"temperature":1.0,"reasoning_tokens":1783,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-16T04:31:54.409525+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take the sequence $RM(0,m)$ with any $p<1/2$: the message space has only two states, the Gibbs transition matrix is $2\\times 2$, and direct diagonalization gives $T_{\\rm mix}=O(1)$ independent of $m$, contradicting the claimed super-polynomial lower bound. This pins the missing hypothesis as $R>0$ (equivalently $r\\ge 1$).","supporting_citations":[{"cited_title":"On α -decodability and α -likelihood decoder,","cited_arxiv_id":null,"evidence_quote":"Supplies the lemma that posterior sampling's error probability is within a factor of two of MAP, which is why sampling-based decoders are worth analyzing."},{"cited_title":"A proof that Reed-Muller codes achieve Shannon capacity on symmetric channels","cited_arxiv_id":"2304.02509","evidence_quote":"Completes the capacity-achieving premise for Reed–Muller codes under MAP by establishing vanishing block-error probability on symmetric channels."}],"review_version":1}