{"id":"c03aabce-1657-4027-aae4-9699872e672a","arxiv_id":"2412.08129","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"For Reed-Muller codes of length 2^m, the RPA decoder provably achieves vanishing error probability over the binary symmetric channel for code orders that grow at most like a constant times log m.","lead":"This paper proves the first mathematical upper bounds on how often the recursive projection-aggregation (RPA) decoder fails for Reed-Muller error-correcting codes sent over a binary symmetric channel. It shows that for codes of blocklength 2^m, the decoder's error probability vanishes when the code order grows at most logarithmically with m.","discovery_kind":"first_principles","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma IV.4 is stated unconditionally but proved from the conditional formula (6); Proposition IV.2's proof therefore skips the probability of a wrong FHT decision, and the aggregation bound needs a repair before Theorem III.1 is fully established.","rationale":"The central claim, Theorem III.1, has a fairly clean recursive structure: the FHT analysis is a standard union bound over Fourier coefficients, and the induction over the projection-aggregation tree is plausible with polynomial prefactors. The reader's identified constant-factor issues are minor and do not affect the asymptotic statements. However, the proof of the aggregation step contains a conditioning gap that is more fundamental than the constant issues: Lemma IV.4 is stated and used unconditionally, while its proof presupposes the event that all projected first-order decoders return zero. This matters because the probability of a wrong FHT decision, delta', is much larger than the Hoeffding probability delta for the relevant eps, so the unconditional 1 - delta bound cannot be obtained by ignoring the G^c contribution. The intended repair is standard and likely succeeds, which is why I would keep the conditional verdict rather than reject the paper. I also note a separate secondary error in Section VI: the observation that eta(p^(r-1)) = eta(p) is false under the paper's own definition of eta, and this appears to affect the higher-dimensional Corollary VI.1; however, the main Theorem III.1 and the abstract's logarithmic-order claim do not rely on that section.","tokens_in":26342,"tokens_out":36673,"duration_ms":377212,"concrete_test":"Formally separate phi from tilde-phi: define tilde-phi(x) by the RHS of (6), prove directly for iid Y_z that Pr(|tilde-phi(x) - phi_infty(x)| <= eps) >= 1 - 2 exp(-2(N-1)eps^2), and then check the chain Pr(Flip^(N)(x)=Y_x) >= 1 - delta - delta' and Pr(Flip^(N)(x)=Y_x | G) >= (1 - delta - 2 delta')/(1 - delta'). If this yields the same conditional bound 1 - 16N(N-1) exp(-N eps^2/8), the aggregation analysis is complete after a presentation correction; if the constants change or the chain fails, Theorems IV.2 and III.1 are not established as written.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Lemma IV.4 is the concentration step on which the aggregation phase (Proposition IV.2, Theorem IV.2, and ultimately Theorem III.1) rests. Its statement is unconditional, but its proof uses identity (6), phi^(N)(x) = (1/(N-1)) sum_{z != x} Y_z when Y_x = 0 (and the symmetric expression when Y_x = 1), which is valid only on the event G that every FHT-projection is decoded to the all-zero word. Off G, the Algorithm-2 count phi(x) = sum_i 1{Y/B_i != hat-Y/B_i} can differ from this expression by an arbitrary amount, and no bound for that difference is given. If Lemma IV.4 is instead read as conditional on G, Hoeffding is applied to coordinates Y_z as though they were iid, but the received vector is not iid conditioned on G. The later subtraction of Pr(G^c) in Proposition IV.2 shows the intended law-of-total-probability route, but the manuscript does not supply the required unconditional concentration of the auxiliary variable tilde-phi(x) (the RHS of (6)); without it, the step from an unconditional probability of 1 - delta to the conditional bound 1 - 2 delta' is not justified. This is repairable, but as written it is a load-bearing missing argument in the main line of the proof.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper analyzes the recursive projection-aggregation (RPA) decoder of Ye and Abbe for Reed-Muller codes over the binary symmetric channel. The main result, Theorem III.1, is an explicit upper bound on the average error probability of RM(m,r) under single-iteration RPA decoding with one-dimensional projections: P_err <= 32 N^{r+1} exp(-2^{-r-1} N epsilon^2) for r >= 2 and 0 < epsilon < eta(p), where eta(p) is expressed in terms of the projected noise level. A corollary gives vanishing error probability for orders r up to roughly log m. The proof proceeds by bounding the ML/FHT error probability for first-order RM projections, analyzing the aggregation step on the event that all projections decode to zero, and then recursively composing these estimates up a projection-aggregation tree. A separate theorem extends the bound to k-dimensional projections.","tokens_in":26576,"tokens_out":12052,"duration_ms":108600,"significance":"If the main theorem is correct, the paper gives the first theoretical guarantee that the RPA decoder, a practical algorithm, achieves vanishing error probability on RM codes of growing order over the BSC. The explicit non-asymptotic bound and the clean separation of the FHT/ML base case, the aggregation step, and the recursive composition are strengths. The proof is self-contained apart from the standard concentration inequalities and the codeword-symmetry fact from [23]. No parameters are fitted; epsilon and delta are arbitrary in their stated ranges. However, the concentration argument for the aggregation step has a load-bearing gap (see major comments), so the manuscript in its current form does not fully establish the main claim.","major_comments":[{"comment":"Lemma IV.4 is stated as an unconditional concentration bound for phi^(N)(x), but its proof uses identity (6), which is valid only on the event G that every FHT projection is decoded to the all-zero word. Off G the actual count phi(x) = sum_i 1{Y/B_i != hat-Y/B_i} can differ from the right-hand side of (6), and the proof gives no bound for that difference. Read as a conditional statement on G, the Hoeffding step would require the coordinates of Y to be i.i.d. after conditioning on G, which is not available. Proposition IV.2 then uses Lemma IV.4 through the law of total probability to get an unconditional closeness-of-indicators bound, and converts it to the conditional bound on G by subtracting Pr(G^c). The missing ingredient is an unconditional concentration statement for the actual phi(x), or a separate bound on the probability that phi(x) differs from the auxiliary variable in (6). This gap is load-bearing: it feeds Theorem IV.2 and, through Theorem V.1, Theorem III.1.","section":"IV-B, Lemma IV.4 and Proposition IV.2"},{"comment":"The same structural gap reappears in the k-dimensional case. Lemma VI.3 proves concentration of the idealized sum sum_{i=1}^{tilde-n} Z_i of coset parities, but phi(x) equals this sum only on the event G_k that all first-order projections at the leaves are decoded to zero. The passage from Lemma VI.3 to the concentration of phi(x), described as 'arguing similar to Lemma IV.4', is not justified off G_k. Consequently the bound in Theorem VI.2, and hence Theorem III.2, inherits the unproved step.","section":"VI, Lemma VI.3 and Theorem VI.2"}],"minor_comments":[{"comment":"The symbol p is used both for the channel crossover probability and for the projected noise level (1-(1-2p)^{2^{r-2}})/2; this is confusing and should be resolved with a distinct symbol such as bar-p.","section":"III, before Theorem III.1"},{"comment":"The notation for the normalized count is circular: the text writes phi(x) = phi^(N)(x) = phi(x)/(N-1). The normalized quantity should be introduced as a separate symbol, e.g., bar-phi(x).","section":"IV-B, aggregation step"},{"comment":"The event G is reused for two different events in the same proof (the event that all projections decode to zero and the concentration event for the normalized count). Renaming one of them would remove ambiguity.","section":"IV-B, proof of Proposition IV.2"},{"comment":"The appeal to '[33, Lemma 1]' is too vague; either state the lemma or provide the short argument, since the cited paper is about coset error patterns and is not a standard background reference.","section":"IV-B, Lemma IV.5"},{"comment":"There are a few typos, including 'probabailities' in Section III and 'straightfoward' in Section VI; a careful proofreading pass is needed.","section":"Throughout"}],"recommendation":"major_revision","confidential_remarks":"The gap in the concentration lemma is likely repairable and does not appear to invalidate the claimed theorem, but the manuscript as written should not be accepted without that repair. The paper's contribution, an explicit non-asymptotic bound for RPA decoding with a logarithmic order growth consequence, is a valuable step and within the journal's scope. The authors should also be asked to clarify the reuse of p and the overloaded event G."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The headline is right: this is the first formal analysis of RPA decoding error probability over the BSC, with vanishing-error guarantees for RM orders up to O(log m). That is a genuine step forward. The projection-aggregation tree is a clean device, and the recursive union-bound structure is sensible. The FHT/ML analysis for first-order RM codes is straightforward but correct. Credit where due: no parameter fitting, explicit bounds, and the asymptotic claim is robust to the constant-level slips.\n\nThe soft spot is real and more serious than the constant-factor issues. Lemma IV.4 is stated unconditionally, but its proof uses identity (6), which is only valid on the event that every FHT-projected word decodes to the all-zero word (the event G in Section IV-B). Off that event, phi(x) can differ arbitrarily from the RHS of (6). The proof of Proposition IV.2 tries to use Lemma IV.4 as an unconditional concentration estimate, then subtracts Pr(G^c) to condition on G. That route only works if you have concentration of the auxiliary variable tilde-phi(x) (the RHS of (6)) unconditionally, or if you prove concentration directly under the conditional distribution. The paper does neither. Conditioned on G, the received coordinates are no longer iid, so the Hoeffding argument does not apply as written. This is a gap in the main line of the proof, not a cosmetic issue.\n\nMinor things: the \"low-complexity\" claim is only accurate for fixed r; Corollary VI.1 appears to drop a 2^{-2r} factor relative to Theorem III.2; and the result bounds a single-iteration convergence event, not the decoder's actual error event, so the claim is on something strictly stronger. The paper is honest that the rate vanishes, which is worth noting.\n\nWho is this for? People working on Reed-Muller decoding algorithms, and to a lesser extent recursive decoding generally. The paper deserves a serious referee because the claimed theorem is significant and the proof structure is mostly sound, but the Lemma IV.4 gap needs to be fixed before the theorem is established. I would send it to peer review with the expectation of major revision: ask the authors to supply a correct unconditional concentration bound or to reformulate the conditioning properly.","headline":"First real analysis of RPA decoding error over the BSC, and the asymptotic claim is likely right, but the main concentration lemma is proved from an identity that only holds under the very conditioning it claims to avoid.","tokens_in":27157,"tokens_out":5043,"would_cite":false,"duration_ms":47035,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["94B35","94B05"],"pacs":[],"model":"deepseek-v4-flash","headline":"The RPA decoder provably drives Reed-Muller error probability to zero for orders up to roughly log m.","keywords":["RPA decoder","Reed-Muller codes","binary symmetric channel","error probability bound","projection-aggregation tree","fast Hadamard transform","vanishing error probability","recursive decoding"],"falsifier":"Run the RPA decoder on a small RM code, for example $\\mathrm{RM}(8,2)$ over BSC$(0.1)$, with both the all-zeros codeword and a random nonzero codeword, using enough trials to distinguish a factor-of-two difference in error rate; a systematic gap would refute the codeword-symmetry reduction on which the bounds rest. At a larger blocklength, compare the measured single-iteration failure rate against the theorem's exponential rate $2^{-r-1} N \\epsilon^2$: if the decay is slower than linear in $N$, the central bound is wrong.","tokens_in":26090,"feed_emoji":"📡","tokens_out":14164,"duration_ms":129899,"temperature":0.7,"pith_summary":"The paper's claim is that the Recursive Projection-Aggregation (RPA) decoder, a practical algorithm previously supported mainly by simulations, can be proved to drive Reed-Muller error probability to zero on the binary symmetric channel (BSC) for code orders $r$ up to roughly $\\log m$, where $N=2^m$ is the blocklength. Its main result is the explicit upper bound $P_{\\mathrm{err}}(\\mathrm{RM}(m,r)) \\le 32 N^{r+1} \\exp(-2^{-r-1} N \\epsilon^2)$, valid for any $\\epsilon < \\eta(p) = \\frac12(1-2p)^{2^{r-1}}$. A direct corollary is that every $r \\le \\log(c m)$ with $c < \\log 2 / \\log(1/(1-2p))$ has vanishing error as $m \\to \\infty$, and that fixed orders $r \\ge 2$ always do. The proof bounds the two RPA subroutines\\textemdash maximum-likelihood decoding of first-order RM projections and the majority-style aggregation step\\textemdash and composes those bounds along the decoder's recursion tree, restricted to the event that every recursive call converges in one iteration.","feed_headline":"RPA decoder provably beats the BSC for Reed-Muller codes","feed_subtitle":"RPA decoding gets a formal error-probability bound, with vanishing error for RM orders up to about log m.","key_machinery":"The projection-aggregation tree is the organizing device: each node is an RM code, each downward move replaces a node by its projections onto subspaces (one-dimensional in the main proof), and each upward move recombines decoded child estimates by the aggregation vote $\\phi(\\mathbf{x}) = \\sum_i \\mathbf{1}\\{Y/B_i([\\mathbf{x}+B_i]) \\ne \\hat{Y}/B_i([\\mathbf{x}+B_i])\\}$, flipping a received symbol when more than half the projections disagree. Two concentration estimates carry the argument: one shows that the Fast Hadamard Transform (ML) decoder on a first-order RM projection concentrates around the true Walsh character, and one shows that the aggregation statistic $\\phi(\\mathbf{x})$ concentrates around $p(1-Y_{\\mathbf{x}})+(1-p)Y_{\\mathbf{x}}$. Composing the resulting per-level failure probabilities along the tree, with the codeword-symmetry reduction to the all-zeros word, yields the bounds of Theorems III.1 and III.2.","core_discovery":"The authors establish that a single iteration of the RPA decoder at every level of its recursion is enough to give a provable error-decay guarantee. Working over the BSC and using one-dimensional projection subspaces, Theorem III.1 bounds $P_{\\mathrm{err}}(\\mathrm{RM}(m,r))$ by $32 N^{r+1} e^{-2^{-r-1} N \\epsilon^2}$ for any $\\epsilon<\\eta(p)$, which yields the logarithmic-order corollary and the decoding-radius statement $N/2(1-\\gamma_m-\\delta)$ for fixed $r$. The same machinery, with Lipschitz concentration in place of Hoeffding, gives a parallel bound for $k$-dimensional subspaces (Theorem III.2) and shows the growth-rate guarantee for $r$ does not improve. The paper is explicit that the results cover only low-rate RM codes: the guaranteed orders have rate tending to zero, and whether RPA achieves positive rate or capacity under the BSC remains open.","pith_inferences":["The single-iteration restriction is the main bottleneck: if correlations across RPA iterations could be controlled, extending the recursion beyond one iteration is the natural route toward orders linear in $m$ and possibly positive rates, a direction the authors flag as future work.","The codeword-symmetry proposition is imported rather than re-proved, so a small-scale simulation comparing all-zeros and nonzero RM codewords under RPA would be the cheapest check of the proof's foundation.","The prefactor $N^{r+1}$ makes the bound's literal value unusably large at moderate blocklengths; the testable content is the exponential decay rate, and simulations should focus on the slope of $\\log P_{\\mathrm{err}}$ versus $N$ rather than on the constant.","Lemma IV.5 predicts a concrete two-iteration improvement for second-order codes\\textemdash a factor-$N$ saving in the failure probability with the same exponent\\textemdash which could be verified or contradicted by simulation before any higher-order extension is attempted."],"forward_implications":["Every fixed order $r\\ge 2$ becomes provably decodable by RPA with vanishing error probability as the blocklength grows.","Orders $r \\le \\log(c m)$, for $c$ below $c(p)=\\log 2/\\log(1/(1-2p))$, also have vanishing error; these codes have vanishing rate, so the guarantee is for low-rate transmission.","For fixed $r$, the decoder corrects $N/2(1-\\gamma_m-\\delta)$ bit flips with high probability for large $m$, giving a concrete decoding-radius statement comparable to prior recursive decoders.","Using $k$-dimensional projection subspaces yields the same asymptotic growth of $r$ with $m$ as the one-dimensional case under this analysis, so higher-dimensional projections do not improve the proven order threshold.","Because the bounds charge any recursive call that fails to converge in one iteration as an error, the theorem's guarantees remain valid\\textemdash and can only be conservative\\textemdash for the full RPA decoder with more iterations."],"supporting_citations":[{"why":"Introduces the RPA decoder and supplies the codeword-symmetry proposition that allows the all-zeros reduction used throughout the paper.","marker":"[23]"},{"why":"Provides the Fast Hadamard Transform implementation of ML decoding used as the leaf subroutine for first-order RM codes.","marker":"[12]"},{"why":"Supplies RM code structure and the FHT/ML decoder background, including the projection property that RM(m,r) projects to RM(m-1,r-1).","marker":"[29]"},{"why":"Hoeffding's inequality, used in Lemmas IV.2-IV.4 to concentrate ML inner products and the aggregation statistic.","marker":"[31]"},{"why":"Bernoulli Lipschitz concentration theorem used in Lemma VI.3 to control correlated subspace sums for k-dimensional projections.","marker":"[34]"},{"why":"Dumer's recursive decoder is the comparison baseline for the decoding-radius statement in Corollary III.2.","marker":"[15]"},{"why":"Prior explicit bounds on ML error probability for first-order RM codes, replaced here by a simpler Hoeffding-based estimate.","marker":"[18]"},{"why":"Coset error-pattern analysis used in Lemma IV.5 for the tighter two-iteration bound on second-order RM codes.","marker":"[33]"}],"fun_headline_variants":["RPA decoding provably kills BSC errors for Reed-Muller codes","Single-step RPA decoding provably defeats BSC for RM codes","RPA decoder: provable vanishing error for RM orders up to log m","Provable BSC error decay for RPA-decoded Reed-Muller codes","RPA decoding: provable error bound for Reed-Muller codes on BSC"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that the error probability is independent of which RM codeword was sent, so bounding the all-zeros word bounds every codeword, and the proof establishes its concentration estimates only for that all-zeros input and only for the event that each recursive RPA call converges in a single iteration.","fun_headline_variants_meta":{"raw":{"variants":["RPA decoding provably kills BSC errors for Reed-Muller codes","Single-step RPA decoding provably defeats BSC for RM codes","RPA decoder: provable vanishing error for RM orders up to log m","Provable BSC error decay for RPA-decoded Reed-Muller codes","RPA decoding: provable error bound for Reed-Muller codes on BSC"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000612,"raw_usage":{"total_tokens":2834,"prompt_tokens":921,"completion_tokens":1913,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":537,"completion_tokens_details":{"reasoning_tokens":1814}},"tokens_in":537,"tokens_out":1913,"duration_ms":12177,"temperature":1.0,"reasoning_tokens":1814,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T18:14:32.880589+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the RPA decoder on a small RM code, for example $\\mathrm{RM}(8,2)$ over BSC$(0.1)$, with both the all-zeros codeword and a random nonzero codeword, using enough trials to distinguish a factor-of-two difference in error rate; a systematic gap would refute the codeword-symmetry reduction on which the bounds rest. At a larger blocklength, compare the measured single-iteration failure rate against the theorem's exponential rate $2^{-r-1} N \\epsilon^2$: if the decay is slower than linear in $N$, the central bound is wrong.","supporting_citations":[{"cited_title":"Recursive projection-aggregation decoding of Reed-Muller codes,","cited_arxiv_id":null,"evidence_quote":"Introduces the RPA decoder and supplies the codeword-symmetry proposition that allows the all-zeros reduction used throughout the paper."},{"cited_title":"Optimal soft decision block decoders based on fast Hadamard transform,","cited_arxiv_id":null,"evidence_quote":"Provides the Fast Hadamard Transform implementation of ML decoding used as the leaf subroutine for first-order RM codes."},{"cited_title":"Reed-Muller codes: Theory and algorithms,","cited_arxiv_id":null,"evidence_quote":"Supplies RM code structure and the FHT/ML decoder background, including the projection property that RM(m,r) projects to RM(m-1,r-1)."},{"cited_title":"Raginsky and I","cited_arxiv_id":null,"evidence_quote":"Bernoulli Lipschitz concentration theorem used in Lemma VI.3 to control correlated subspace sums for k-dimensional projections."},{"cited_title":"Recursive decoding and its performance for low-rate Reed-Muller codes,","cited_arxiv_id":null,"evidence_quote":"Dumer's recursive decoder is the comparison baseline for the decoding-radius statement in Corollary III.2."},{"cited_title":"Error exponents for recursive decoding of Reed–Muller codes on a binary-symmetric channel,","cited_arxiv_id":null,"evidence_quote":"Prior explicit bounds on ML error probability for first-order RM codes, replaced here by a simpler Hoeffding-based estimate."},{"cited_title":"Coset error patterns in recursive projection-aggregation decoding,","cited_arxiv_id":null,"evidence_quote":"Coset error-pattern analysis used in Lemma IV.5 for the tighter two-iteration bound on second-order RM codes."}],"review_version":1}