Capacity on BMS Channels via Code Symmetry and Nesting

Galen Reeves; Henry D. Pfister

REVIEW 3 major objections 4 minor 2 cited by

Capacity on BMS Channels via Code Symmetry and Nesting

T0 review · 3 major / 4 minor · reviewed 2026-08-16 · deepseek-v4-flash

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

Pith's one-line read This paper proves recursive two-look and three-look nesting bounds that make the bit-error probability of Reed–Muller codes decay exponentially at rates near capacity on every binary memoryless symmetric channel.

desk verdict A clean, honest reproof of known RM-capacity results, with a real gap: the BSC chain is solid, while the general BMS chain rests on an unproven real-variable variance bound the authors explicitly say is proved only for boolean functions. read the letter →

arxiv 2504.15394 v1 pith:LI45WV3V submitted 2025-04-21 cs.IT math.IT

Henry D. Pfister , Galen Reeves This is my paper · ORCID

classification cs.ITmath.IT MSC 94B0594B3594A24

keywords Reed-Mullercodescapacity-achievingbinarymemorylesssymmetricchannelsbit-MAPdecodingblock-MAPbooleanfunctionanalysishypercontractivitycodenesting

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

This paper tries to establish a single recursive mechanism by which sequences of highly symmetric, strongly nested linear codes—the flagship case being binary Reed–Muller codes—achieve capacity on every binary memoryless symmetric (BMS) channel. The mechanism places two partially overlapping punctured copies of a short code inside a longer code, producing two weakly correlated estimates of a distinguished transmitted bit, and a symmetry variance bound for the decoding function controls that correlation by the fractional overlap. Iterating the two-look recursion yields bit-error probability that decays exponentially in the number of nesting stages while the code rate approaches capacity. For the binary symmetric channel, a three-look majority-vote recursion sharpened by level-k hypercontractivity gives a faster decay, and a weight-enumerator list-decoding step converts that faster decay into vanishing block error probability. A final transfer argument extends such BSC block-error bounds to any BMS channel with equal or larger capacity, provided the minimum distance grows faster than logarithmically.

What carries the argument

The central object is the extrinsic decoding function for one distinguished bit, viewed as a real function of the channel noise variables and inheriting the code's automorphism symmetries. Lemma 31 is the load-bearing identity: for any subset $A$ of variables, $\mathrm{Var}(E[f \mid X_A])$ equals a sum over Fourier sets weighted by $P(\Pi(S) \subseteq A)$, which for a transitive symmetry group is bounded by $|A|/n$ and for $\mathrm{GL}(m,2)$ symmetry by $2^{-\ell\,\dim(S)}$. Nesting supplies two (or three) overlapping projections $C'=C|_{\{0\}\cup A\cup B}$ and $C''=C|_{\{0\}\cup A\cup C}$ of the shorter code inside the longer one, so the same bit is estimated from nearly disjoint observation sets; Lemma 16 interpolates the correlation of the two estimates between independence and perfect correlation as the overlap varies. Optimizing the combining coefficient $\alpha$ in the two-look estimator gives the recursion $M(C) \le (1+\rho)M(C')/(2-(1-\rho)M(C'))$, and for the BSC the level-k inequality sharpens the variance bound at small error values, producing the faster decay via Lemma 44.

What would settle it

Take a real-output BMS channel (for instance, additive Gaussian noise after BPSK) and a small symmetric code, define $f(y_{\sim 0}) = E[X_0 \mid Y_{\sim 0} = y_{\sim 0}]$, and compute $\mathrm{Var}(E[f \mid Y_A])$ for the two-look partition $A,B$; if the ratio to $\mathrm{Var}(f)$ exceeds $\rho = |A|/(|A|+|B|)$ for any such partition, the unproved ANOVA extension fails and Lemma 28's recursion is false for general BMS channels. For the BSC claims, a finite-length simulation of bit-MAP decoding on RM$(r,m+k)$ for moderate $m,k$ could look for a violation of the stated exponential-$k$ bound at the advertised rate gap.

Watch

Extended reading notes

Core claim

On its own terms, the paper claims that a strongly nested sequence of doubly transitive codes with normalized overlap $\rho<1$ has bit-MAP error bounded by $P_b(C_k) \le ((1+\rho)/2)^k (1-\delta)/\delta$ on any BMS channel, whenever the base code's rate sits $\delta$ below capacity. For the binary symmetric channel the claimed improvement is $P_b(C_k) \le \exp(-\frac{1}{8} k \ln(ek/2\eta))$ for RM codes $C_k = \mathrm{RM}(r,m+k)$ with $k$ divisible by 8, so choosing $k=2\eta\sqrt{m}$ exchanges a rate gap of at most $\delta+\eta$ for bit error decaying exponentially in $\sqrt{m}\ln m$. These bit-error bounds are combined with a weight-enumerator list-decoding bound to claim vanishing block-MAP error at rates arbitrarily close to capacity, and with an isoperimetric transfer to claim the same on every BMS channel whose capacity is at least that of the relevant BSC. The claims are stated as unconditional performance bounds for the code sequences under optimal extrinsic MAP decoding.

Load-bearing premise

The load-bearing premise is that Lemma 31 extends from real functions of i.i.d. boolean variables to real functions of arbitrary i.i.d. real random variables through the ANOVA decomposition; Remark 34 asserts this extension but the paper's proof is given only for the BSC, so if the extension fails the general BMS recursion (Lemma 28 and Theorem 30) collapses while the BSC-only results remain.

Editorial extensions

If this is right

Reed–Muller codes achieve capacity under bit-MAP decoding on every BMS channel, with bit-error probability decaying exponentially in the number of nesting stages for any fixed gap to capacity.
On the BSC, the three-look recursion gives the faster bound $P_b(C_k)\le \exp(-\frac18 k \ln(ek/2\eta))$, and choosing $k=2\eta\sqrt{m}$ makes the error decay exponentially in $\sqrt{m}\ln m$ while the rate is at most $\delta+\eta$ below capacity.
Combining the fast bit-error bound with the weight-enumerator list-decoding argument yields vanishing block-MAP error for RM codes at rates arbitrarily close to capacity.
Any strongly nested doubly transitive sequence with normalized overlap bounded away from 1 inherits the exponential two-look bound; the RM family is the concrete sequence where the rate cost per nesting stage vanishes.
A code sequence whose minimum distance grows like $\omega(\ln N)$ and whose block error on the BSC is below $1-1/N^2$ has vanishing block error on every BMS channel with at least the same capacity.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

If the ANOVA extension asserted in Remark 34 really holds, the same two-look recursion should extend to other symmetric alphabets and channel models, since the boolean argument in Lemma 28 only uses the binary alphabet through the variance bound.
The recursive two-look estimator resembles a soft projection-aggregation decoder; a testable finite-length prediction is that truncated recursions on small RM codes still follow the same exponential trend as the reported bound.
A natural optimization left implicit is the tradeoff between the number of looks per stage and the fractional overlap: three looks cost four code lengths per stage in the RM construction, so larger look counts might reproduce the sun-flower gains without floral geometry if the correlation bound can be sharpened.
Theorem 48's transfer is independent of the RM analysis, so any future code family meeting the minimum-distance and BSC block-error assumptions inherits near-capacity behavior on all weaker BMS channels.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

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

Desk Editor's Note

read the letter

Colleague, read this if you want a version of the Reeves-Pfister / Abbe-Sandon machinery without sunflowers. The paper does two things well. It gives a recursive two-look bound for BMS channels and a three-look plus level-k bound for the BSC, and it proves an explicit transfer theorem (Thm 48) from BSC block-error behavior to arbitrary BMS channels. The BSC analysis is careful and mostly self-contained, and the authors are unusually candid about what is and is not proved.

The new material is real but modest. The capacity results are not new: RM codes achieving capacity on BMS channels under bit-MAP is [8], and vanishing block error on the BSC is [9]. The contribution is showing you can get the same rates with a simpler recursive argument and fewer looks, and that the level-k inequality can replace sunflowers. That is worth having, especially Theorem 48, which pins down a folk theorem cleanly.

The soft spot is exactly where the stress-test places it. Lemma 28 and Theorem 30 depend on Lemma 31 holding for real functions of i.i.d. real random variables, but the proof in Section V is for boolean variables. Remark 34 says the general case follows from an ANOVA decomposition and cites a private communication [35]. The authors themselves write, 'strictly speaking, the proof in this paper is given only for the case of the BSC.' That is a load-bearing gap for the general BMS theorem. The BSC-only chain does not share the gap, and Theorem 48 uses only BSC block-MAP, so that portion stands on its own.

I would not desk-reject this. Send it to referees. A referee should push for either a public proof of the ANOVA extension or a statement restricting the BMS theorem to a form the proof actually covers. If the gap closes, this becomes a standard reference for the simplified approach. If not, the BSC portion still deserves publication.

Referee Report

3 major / 4 minor

Summary. The paper develops unified recursive bounds for the bit-MAP error probability of nested doubly transitive code sequences. The BMS analysis (Sections IV and V) uses a two-look recursion and a symmetry variance bound to obtain error probability decaying exponentially in the number of nesting stages; the BSC analysis (Section VI) uses three looks, a biased level-k inequality, and hypercontractivity to obtain a faster decay that, combined with weight-enumerator/list-decoding arguments, yields vanishing block error probability. Section VII transfers BSC block-error bounds to general BMS channels under a minimum-distance growth condition. The main theorems are Theorem 30 (BMS bit-MAP), Theorem 45 and Corollary 46 (BSC faster decay and vanishing block error), and Theorem 48 (BMS block-error transfer).

Significance. Assuming the BMS step is completed, the paper gives a substantially simplified and unified route to the known result that RM codes achieve capacity on BMS channels under bit-MAP and block-MAP decoding, with explicit exponential decay rates and without relying on subspace sunflowers. The BSC portion is largely self-contained and includes detailed proofs with named constants, which is a genuine strength. The current manuscript, however, contains a self-admitted gap in the BMS analysis (Lemma 28 and Theorem 30) and a tie-breaking/symmetry issue in the BSC fast-decay argument; until those are resolved, the paper's title-level claim of capacity on BMS channels is not fully supported. The paper is honest about the BMS gap, which helps the reader but does not remove the need to fill it.

major comments (3)

[§IV-B, Lemma 28 and Theorem 30; Remark 34] The BMS recursion is not proven as written. Lemma 28 applies Lemma 31 to the real-valued conditional-mean function f on i.i.d. real noise variables, but Section V proves Lemma 31 only for real functions of boolean variables: the proof uses the finite Fourier basis {u_S} and the vanishing of E[u_S(X)] for nonempty S, and the identity (10) is a sum over scalar coefficients. For arbitrary real variables the ANOVA subspaces indexed by subsets are infinite-dimensional and the argument does not transfer. The proof of Lemma 28 explicitly states 'strictly speaking, the proof in this paper is given only for the case of the BSC,' and Remark 34 attributes the needed generalization to a private communication [35]. Since Theorem 30 is the paper's main BMS bit-MAP capacity statement, this is a load-bearing gap. The authors should either supply a complete proof of the variance bound Var(E[f(Z_A)|Z_A]) <= rho Var(f(Z_A,Z_B)) for real-valued f with transitive symmetry and arbitrary i.i.d. real Z, or restrict the BMS claims and revise the title and abstract accordingly.
[§VI-A, §V-B (Corollary 33 and Lemma 36)] The faster BSC bound requires GL(m,2) symmetry of the bit-MAP decoding function, but the tie-breaking used to define f is arbitrary. The text preceding Corollary 33 concedes that applying linear transformations to an optimal decoding function may change only tie-breaking; however a fixed arbitrary tie-breaking rule need not be GL-equivariant on the whole Boolean cube, so Sym(f) may be strictly smaller than GL(m,2). The fact that bit-error probability is independent of tie-breaking does not imply pointwise equivariance, and the proofs of Lemma 44 and Theorem 45 use the pointwise symmetry bound (14). Please specify a tie-breaking rule that is GL-equivariant (or prove that one exists) and ensure it is used consistently in Section VI.
[§VII, Theorem 48] The transfer from BSC block-error bounds to general BMS channels rests on [25, Proposition 7.1], which is cited by page number but not stated. Since Theorem 48 is the only route from the BSC results to block-MAP capacity on arbitrary BMS channels, the proposition should be stated (or proved) in the paper, including its exact hypotheses on the code and channel. Without this, the final BMS block-error claim cannot be checked from the manuscript.

minor comments (4)

[§III-A and §IV-A, Lemmas 19 and 28] The condition C' = C'' is ambiguous because the two projections live on different coordinate subsets; please state explicitly that they are equivalent under the identification of B with C and that the decoding function f has transitive symmetry.
[Theorem 2 and Section I-B] There are small typos in the displayed statements and outline, for example 'F or' instead of 'For' at the start of Theorem 2; please proofread.
[Theorems 40 and 45] The constant c(p)=1/(8 ln(1/min{p,1-p})) is defined in Lemma 35 but used without recall in later proofs; please redefine it near each use for readability.
[Theorem 48] The hypothesis B_m(p) <= 1 - 1/N_m^2 is a weak near-one bound, and the statement is easier to read if this is clarified before the amplification step.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity found: recursive bounds are derived from explicit symmetry and external theorems; the acknowledged BMS proof gap is a correctness risk, not circularity.

full rationale

The derivation is not circular. In Section IV, Lemma 28 and Lemma 29 derive the MMSE recursion from the symmetry variance bound (Lemma 31), the two-look RM construction, and the EXIT-area theorem (proved in Appendix C as Theorems 49 and 50); the code and rate parameters r,m,t,k are fixed in advance from the target capacity gap, not fitted to the final bound. Theorem 45 and Corollary 46 then apply hypercontractivity (Lemma 35) and the external list-decoding/weight-enumerator step [9, Lemma 9]. None of these inputs is the target conclusion, and no predicted quantity is defined in terms of a fit. Lemma 13 and the overlapping RM-look construction are restated with proofs or explicit subspace definitions, so the two-look property is not reduced to a bare self-citation. The paper itself flags the one genuine gap: Remark 34 and the proof of Lemma 28 state that the general-BMS use of Lemma 31 for real i.i.d. random variables is proven only for the BSC, with the real-variable ANOVA extension attributed to private communication [35]. That is an omitted-proof and correctness risk for the BMS portion, not a circular step, because the needed ANOVA bound would be an independent mathematical fact and the BSC-only chain (Theorems 45 and Corollary 46) does not rely on it. Self-citations to [8], [18], and [31] supply background and prior constructions but are not load-bearing in the derivation. No circular step can be exhibited.

Assumptions & free parameters 0 free parameters · 7 assumptions · 0 invented entities

The central results depend on standard tools of boolean function analysis, the EXIT area theorem, and known properties of RM codes. The only nonstandard ingredient is the unproven ANOVA extension of Lemma 31, which is load-bearing for the BMS claims and explicitly flagged by the authors.

assumptions (7)

domain assumption BMS channel outputs decompose as Y_i = X_i Z_i with Z_i i.i.d. and independent of X
Standard BMS model cited to [26, p.182], used in Section IV-A to define the conditional-mean decoding function.
domain assumption Extrinsic decoding functions (bit-MAP or conditional mean) inherit the transitivity or GL(m,2) symmetry of the code
Used in Lemma 31 and Corollary 33 to bound the variance of a restriction; the paper argues this through code automorphisms.
domain assumption The strong nesting property with normalized overlap rho=1/2 (and three looks with rho=1/4) holds for RM(r,m+k) sequences
Derived from Lemma 13 and the subspace construction in Section II-F; it is the basis for all recursive bounds.
standard math The biased level-k inequality for boolean functions (Lemma 35) holds as stated
Proved in Appendix D.3 from hypercontractivity in [12, Corollary 10.20]; the paper provides a proof sketch.
standard math The EXIT area theorem and the MMSE/BER relations (Theorems 49 and 50) hold
Used to lower-bound the initial gap delta = C - R(C0); standard results from [33] and [18].
ad hoc to paper Lemma 31 extends to real functions of arbitrary i.i.d. real random variables via the ANOVA decomposition
Stated in Remark 34 and attributed to a private communication [35]; no proof is given, and the authors note the BMS proof is only shown for the BSC.
standard math The Tillich-Zemor isoperimetric inequality and Sassoglu's transfer result hold as cited
Used in Theorem 48 to transfer BSC block-error bounds to arbitrary BMS channels; combined from [22] and [25].

how reviews work

0 comments

Cite this review

Pith. "Pith review of Capacity on BMS Channels via Code Symmetry and Nesting." pith.science (2026). https://pith.science/paper/LI45WV3V

@misc{pith2026250415394,
  author       = {Pith},
  title        = {Pith review of: Capacity on BMS Channels via Code Symmetry and Nesting},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/LI45WV3V}},
  note         = {Machine review of arXiv:2504.15394}
}

read the original abstract

The past decade has seen notable advances in our understanding of structured error-correcting codes, particularly binary Reed--Muller (RM) codes. While initial breakthroughs were for erasure channels based on symmetry, extending these results to the binary symmetric channel (BSC) and other binary memoryless symmetric (BMS) channels required new tools and conditions. Recent work uses nesting to obtain multiple weakly correlated "looks" that imply capacity-achieving performance under bit-MAP and block-MAP decoding. This paper revisits and extends past approaches, aiming to simplify proofs, unify insights, and remove unnecessary conditions. By leveraging powerful results from the analysis of boolean functions, we derive recursive bounds using two or three looks at each stage. This gives bounds on the bit error probability that decay exponentially in the number of stages. For the BSC, we incorporate level-k inequalities and hypercontractive techniques to achieve the faster decay rate required for vanishing block error probability. The results are presented in a semitutorial style, providing both theoretical insights and practical implications for future research on structured codes.

Figures

Figures reproduced from arXiv: 2504.15394 by the authors.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 2 Pith papers

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

Improved Strongly Polynomial Work-Span Tradeoffs for Directed Single Source Shortest Paths
cs.DS 2026-07 conditional novelty 8.0 of 10

For any t, directed shortest paths can be computed with near-linear work plus n^{1+o(1)}t^2 work and roughly n/t parallel depth, matching the undirected tradeoff.
Density Evolution of Soft-Decision Collapsed Projection-Aggregation Decoding for Reed-Muller Codes over the BIAWGN Channel
cs.IT 2026-07 conditional novelty 6.0 of 10

Soft CPA decoding of RM codes is exact-marginal and symmetric; density evolution (with hard-decision approximations) captures its rapid soft-information collapse and yields vanishing error only at vanishing rate.

Reference graph

Works this paper leans on

44 extracted references · 40 canonical work pages · cited by 2 Pith papers

[8]

Reed–Muller codes on BMS chan nels achieve vanishing bit-error probability for all rates below capacity,

G. Reeves and H. D. Pﬁster, “Reed–Muller codes on BMS chan nels achieve vanishing bit-error probability for all rates below capacity,” IEEE Trans. Inform. Theory , 2023

work page 2023
[9]

A proof that Reed-Muller codes ach ieve Shannon capacity on symmetric channels,

E. Abbe and C. Sandon, “A proof that Reed-Muller codes ach ieve Shannon capacity on symmetric channels,” in Proc. IEEE Symp. on the F ound. of Comp. Sci. , pp. 177–193, 2023

work page 2023
[35]

Anatharam

V . Anatharam. private communication, 2025

work page 2025
[1]

Application of Boolean algebra to switching circuit design and to error detection,

D. Muller, “Application of Boolean algebra to switching circuit design and to error detection,” IRE Trans. Inform. Theory , vol. EC-3, pp. 6–12, Sept. 1954

work page 1954
[2]

A class of multiple-error-correcting codes an d the decoding scheme,

I. Reed, “A class of multiple-error-correcting codes an d the decoding scheme,” IRE Trans. Inform. Theory, vol. 4, pp. 38–49, September 1954

work page 1954
[3]

Reed-Muller code s for random erasures and errors,

E. Abbe, A. Shpilka, and A. Wigderson, “Reed-Muller code s for random erasures and errors,” IEEE Trans. Inform. Theory , vol. 61, pp. 5229–5252, Oct 2015. 27

work page 2015
[4]

Reed-Muller codes achieve capacity on erasure channels,

S. Kudekar, S. Kumar, M. Mondelli, H. D. Pﬁster, E. ¸ Sa¸ so ˘glu, and R. Urbanke, “Reed-Muller codes achieve capacity on erasure channels,” in Proc. of the Annual ACM Symp. on Theory of Comp. , 2016

work page 2016
[5]

Reed-Muller codes achieve capacity on erasure channels,

S. Kudekar, S. Kumar, M. Mondelli, H. D. Pﬁster, E. ¸ Sa¸ so ˘glu, and R. Urbanke, “Reed-Muller codes achieve capacity on erasure channels,” IEEE Trans. Inform. Theory , vol. 63, no. 7, pp. 4298–4316, 2017

work page 2017

Show all 44 references

[6]

Reed-Muller codes polarize,

E. Abbe and M. Y e, “Reed-Muller codes polarize,” IEEE Trans. Inform. Theory , vol. 66, no. 12, pp. 7311–7332, 2020

2020
[7]

On codes dec oding a constant fraction of errors on the BSC,

J. H ˛ azła, A. Samorodnitsky, and O. Sberlo, “On codes dec oding a constant fraction of errors on the BSC,” in Proc. of the Annual ACM Symp. on Theory of Comp. , pp. 1479–1488, 2021

2021
[10]

Reed–Muller C odes,

E. Abbe, O. Sberlo, A. Shpilka, and M. Y e, “Reed–Muller C odes,” F oundations and Trends® in Communications and Information Theory, vol. 20, no. 1–2, pp. 1–156, 2023

2023
[11]

Beyond doubl e transitivity: Capacity-achieving cyclic codes on erasur e channels,

S. Kumar, R. Calderbank, and H. D. Pﬁster, “Beyond doubl e transitivity: Capacity-achieving cyclic codes on erasur e channels,” in Proc. IEEE Inform. Theory W orkshop , pp. 241–245, Sept 2016

2016
[12]

O’Donnell, Analysis of boolean functions

R. O’Donnell, Analysis of boolean functions . Cambridge University Press, 2014

2014
[13]

The inﬂuence of variab les on boolean functions,

J. Kahn, G. Kalai, and N. Linial, “The inﬂuence of variab les on boolean functions,” in Proc. IEEE Symp. on the F ound. of Comp. Sci., pp. 68–80, Oct 1988

1988
[14]

On Russo’s approximate zero-one law,

M. Talagrand, “On Russo’s approximate zero-one law,” The Ann. of Prob. , pp. 1576–1587, 1994

1994
[15]

Every monotone graph propert y has a sharp threshold,

E. Friedgut and G. Kalai, “Every monotone graph propert y has a sharp threshold,” Proc. Amer . Math. Soc. , vol. 124, no. 10, pp. 2993–3002, 1996

1996
[16]

Inﬂuences of variables and th reshold intervals under group symmetries,

J. Bourgain and G. Kalai, “Inﬂuences of variables and th reshold intervals under group symmetries,” Geometric & Functional Analysis , vol. 7, no. 3, pp. 438–461, 1997

1997
[17]

An upper bound on ℓq norms of noisy functions,

A. Samorodnitsky, “An upper bound on ℓq norms of noisy functions,” IEEE Trans. Inform. Theory , vol. 66, no. 2, pp. 742–748, 2019

2019
[18]

Achieving capacity on non-b inary channels with generalized Reed–Muller codes,

G. Reeves and H. D. Pﬁster, “Achieving capacity on non-b inary channels with generalized Reed–Muller codes,” in Proc. IEEE Int. Symp. Inform. Theory , 2023

2023
[19]

Reed-Muller codes: Thresholds and wei ght distribution,

M. Mondelli, S. Kudekar, S. Kumar, H. Pﬁster, E. ¸ Sa¸ so ˘glu, and R. Urbanke, “Reed-Muller codes: Thresholds and wei ght distribution,” in Proc. IEEE Intl. Zurich Seminar on Commun. , (Zurich, Switzerland), p. 50, 2016

2016
[20]

Threshold effects in codes,

G. Zémor, “Threshold effects in codes,” in Algebraic Coding: First French-Israeli W orkshop Paris, France, July 19–21, 1993 , pp. 278– 286, 1994

1993
[21]

Probabilistic characteristics of gra phs with large connectivity,

G. A. Margulis, “Probabilistic characteristics of gra phs with large connectivity,” Problems of Inform. Transm. , vol. 10, no. 2, pp. 101– 108, 1974

1974
[22]

Discrete isoperimetric in equalities and the probability of a decoding error,

J.-P . Tillich and G. Zémor, “Discrete isoperimetric in equalities and the probability of a decoding error,” Combinatorics, Probability and Computing , vol. 9, no. 05, pp. 465–479, 2000

2000
[23]

The Gaussian isoperimetri c inequality and decoding error probabilities for the Gauss ian channel,

J.-P . Tillich and G. Zémor, “The Gaussian isoperimetri c inequality and decoding error probabilities for the Gauss ian channel,” IEEE Trans. Inform. Theory , vol. 50, pp. 328–331, Feb 2004

2004
[24]

On the performance of Reed-Mu ller codes with respect to random errors and erasures,

O. Sberlo and A. Shpilka, “On the performance of Reed-Mu ller codes with respect to random errors and erasures,” in Proc. of the Annual ACM-SIAM Symp. on Discrete Algorithms , pp. 1357–1376, SIAM, 2020

2020
[25]

¸ Sa¸ so˘glu, Polar Coding Theorems for Discrete Systems

E. ¸ Sa¸ so˘glu, Polar Coding Theorems for Discrete Systems . PhD thesis, ÉCOLE POL YTECHNIQUE FÉDÉRALE DE LAUSANNE,
[26]

T. J. Richardson and R. L. Urbanke, Modern Coding Theory . New Y ork, NY: Cambridge University Press, 2008

2008
[27]

Recursive projection-aggregation d ecoding of Reed-Muller codes,

M. Y e and E. Abbe, “Recursive projection-aggregation d ecoding of Reed-Muller codes,” IEEE Trans. Inform. Theory , vol. 66, no. 8, pp. 4948–4965, 2020

2020
[28]

An upper bound on the err or probability of RPA decoding of Reed-Muller codes over the BSC,

V . A. Rameshwar and V . Lalitha, “An upper bound on the err or probability of RPA decoding of Reed-Muller codes over the BSC,” arXiv preprint arXiv:2412.08129 , 2024

2024 arXiv
[29]

Recu rsive subproduct codes with Reed-Muller-like structure,

A. Siddheshwar, L. P . Natarajan, and P . Krishnan, “Recu rsive subproduct codes with Reed-Muller-like structure,” in Proc. IEEE Int. Symp. Inform. Theory , pp. 291–296, IEEE, 2024

2024
[30]

Berman codes: A genera lization of Reed–Muller codes that achieve BEC capacity,

L. P . Natarajan and P . Krishnan, “Berman codes: A genera lization of Reed–Muller codes that achieve BEC capacity,” IEEE Trans. Inform. Theory , vol. 69, no. 11, pp. 6956–6980, 2023

2023
[31]

Reed–Muller codes achieve c apacity on the BEC: A tutorial introduction,

H. D. Pﬁster and G. Reeves, “Reed–Muller codes achieve c apacity on the BEC: A tutorial introduction,” 2025. To appea r on arXiv

2025
[32]

Reed-Muller codes achieve c apacity on BMS channels

G. Reeves and H. D. Pﬁster, “Reed-Muller codes achieve c apacity on BMS channels.” [Online]. Available: https://arxiv.org/abs/2110.14631v2, 2021

2021 arXiv
[33]

Extrinsic in formation transfer functions: model and erasure channel pr operties,

A. Ashikhmin, G. Kramer, and S. ten Brink, “Extrinsic in formation transfer functions: model and erasure channel pr operties,” IEEE Trans. Inform. Theory , vol. 50, pp. 2657–2674, Nov. 2004

2004
[34]

Reed-Muller codes have vanishin g bit-error probability below capacity: a simple tighter pr oof via camellia boosting,

E. Abbe and C. Sandon, “Reed-Muller codes have vanishin g bit-error probability below capacity: a simple tighter pr oof via camellia boosting,” arXiv preprint arXiv:2312.04329 , 2023

2023 arXiv
[36]

Comparing the bit-MAP and block-MAP decoding thr esholds of Reed-Muller codes on BMS channels,

S. Kudekar, S. Kumar, M. Mondelli, H. D. Pﬁster, and R. L. Urbanke, “Comparing the bit-MAP and block-MAP decoding thr esholds of Reed-Muller codes on BMS channels,” in Proc. IEEE Int. Symp. Inform. Theory , (Barcelona, Spain), pp. 1755–1759, 2016

2016
[37]

From bit to bloc k: Decoding on erasure channels,

H. D. Pﬁster, O. Sprumont, and G. Zémor, “From bit to bloc k: Decoding on erasure channels,” in Proc. IEEE Int. Symp. Inform. Theory, IEEE, 2025. Accepted. [Online]. Available: https://arxi v.org/pdf/2501.05748

2025 arXiv
[38]

Reed–Muller codes on CQ chan nels via a new correlation bound for quantum observables,

A. Mandal and H. D. Pﬁster, “Reed–Muller codes on CQ chan nels via a new correlation bound for quantum observables,” i n Proc. IEEE Int. Symp. Inform. Theory , IEEE, 2025. Accepted. [Online]. Available: https://arxi v.org/pdf2502.03785

2025 arXiv
[39]

On the normal approximation to s ymmetric binomial distributions,

C. Hipp and L. Mattner, “On the normal approximation to s ymmetric binomial distributions,” Theory of Probability & Its Applications , vol. 52, no. 3, pp. 516–523, 2008

2008
[40]

Cyclic orbit codes,

A.-L. Trautmann, F. Manganiello, M. Braun, and J. Rosen thal, “Cyclic orbit codes,” IEEE Trans. Inform. Theory , vol. 59, no. 11, pp. 7386–7404, 2013

2013
[41]

Convergence of iterative decoding,

S. ten Brink, “Convergence of iterative decoding,” Electronic Letters, vol. 35, pp. 806–808, May 1999

1999
[42]

Maxwell co nstruction: The hidden bridge between iterative and maximu m a posteriori decoding,

C. Méasson, A. Montanari, and R. L. Urbanke, “Maxwell co nstruction: The hidden bridge between iterative and maximu m a posteriori decoding,” IEEE Trans. Inform. Theory , vol. 54, pp. 5277–5307, Dec. 2008. 28

2008
[43]

Boolean functions with low average sensi tivity depend on few coordinates,

E. Friedgut, “Boolean functions with low average sensi tivity depend on few coordinates,” Combinatorica, vol. 18, no. 1, pp. 27–35, 1998. APPENDIX A DEFERRED PROOFS A.1 Proof of Lemma 13 Proof. For C = RM(r,m ), it is well-known that R(C) = P [Bin(m) ≤r] with P [Bin(m) ≤r] := ...

1998
[2011]

http://infoscience.epﬂ.ch/record/168993

Pith tools

Reviewed August 16, 2026 · model on record in the stance chip above.

[1] [8]

Reed–Muller codes on BMS chan nels achieve vanishing bit-error probability for all rates below capacity,

G. Reeves and H. D. Pﬁster, “Reed–Muller codes on BMS chan nels achieve vanishing bit-error probability for all rates below capacity,” IEEE Trans. Inform. Theory , 2023

work page 2023

[2] [9]

A proof that Reed-Muller codes ach ieve Shannon capacity on symmetric channels,

E. Abbe and C. Sandon, “A proof that Reed-Muller codes ach ieve Shannon capacity on symmetric channels,” in Proc. IEEE Symp. on the F ound. of Comp. Sci. , pp. 177–193, 2023

work page 2023

[3] [35]

Anatharam

V . Anatharam. private communication, 2025

work page 2025

[4] [1]

Application of Boolean algebra to switching circuit design and to error detection,

D. Muller, “Application of Boolean algebra to switching circuit design and to error detection,” IRE Trans. Inform. Theory , vol. EC-3, pp. 6–12, Sept. 1954

work page 1954

[5] [2]

A class of multiple-error-correcting codes an d the decoding scheme,

I. Reed, “A class of multiple-error-correcting codes an d the decoding scheme,” IRE Trans. Inform. Theory, vol. 4, pp. 38–49, September 1954

work page 1954

[6] [3]

Reed-Muller code s for random erasures and errors,

E. Abbe, A. Shpilka, and A. Wigderson, “Reed-Muller code s for random erasures and errors,” IEEE Trans. Inform. Theory , vol. 61, pp. 5229–5252, Oct 2015. 27

work page 2015

[7] [4]

Reed-Muller codes achieve capacity on erasure channels,

S. Kudekar, S. Kumar, M. Mondelli, H. D. Pﬁster, E. ¸ Sa¸ so ˘glu, and R. Urbanke, “Reed-Muller codes achieve capacity on erasure channels,” in Proc. of the Annual ACM Symp. on Theory of Comp. , 2016

work page 2016

[8] [5]

Reed-Muller codes achieve capacity on erasure channels,

S. Kudekar, S. Kumar, M. Mondelli, H. D. Pﬁster, E. ¸ Sa¸ so ˘glu, and R. Urbanke, “Reed-Muller codes achieve capacity on erasure channels,” IEEE Trans. Inform. Theory , vol. 63, no. 7, pp. 4298–4316, 2017

work page 2017