Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

ACM Symposium on Theory of Computing (STOC)

On codes decoding a constant fraction of errors on the BSC

Jan Hązła, Alex Samorodnitsky, Ori Sberlo

Published Jun 15, 2021• 15 citations
Publisher

Abstract

We strengthen the results from a recent work by the second author, achieving bounds on the weight distribution of binary linear codes that are successful under block-MAP (as well as bit-MAP) decoding on the BEC. We conclude that a linear code that is successful on the BEC can also decode over a range of binary memoryless symmetric (BMS) channels. In particular, applying the result of Kudekar, Kumar, Mondelli, Pfister, Şaşoğlu and Urbanke from STOC 2016, we prove that a Reed–Muller code of positive rate R decodes errors on the p with high probability if p < 1/2 − √2−R(1−2−R).

DOI
10.1145/3406325.3451015

Related papers

A Criterion for Decoding on the BSC

Anup Rao, Oscar Sprumont

We present an approach to showing that a linear code is resilient to random errors. We use this approach to obtain decoding results for both transitive codes and Reed-Muller codes. We give three kinds of results about linear codes in general, and transitive linear codes in particular. 1) We give a tight bound on the weight distribution of every transitive linear code $C \subseteq \mathbb{F}_2^N$: $\Pr_{c \in C}[|c| = αN] \leq 2^{-(1-h(α)) \mathsf{dim}(C)}$. 2) We give a criterion that certifies that a linear code $C$ can be decoded on the binary symmetric channel. Let $K_s(x)$ denote the Krawtchouk polynomial of degree $s$, and let $C^\perp$ denote the dual code of $C$. We show that bounds on $\mathbb{E}_{c \in C^{\perp}}[ K_{εN}(|c|)^2]$ imply that $C$ recovers from errors on the binary symmetric channel with parameter $ε$. Weaker bounds can be used to obtain list-decoding results using similar methods. One consequence of our criterion is that whenever the weight distribution of $C^\perp$ is sufficiently close to the binomial distribution in some interval around $\frac{N}{2}$, $C$ is resilient to $ε$-errors. 3) We combine known estimates for the Krawtchouk polynomials with our weight bound for transitive codes, and with known weight bounds for Reed-Muller codes, to obtain list-decoding results for both these families of codes. In some regimes, our bounds for Reed-Muller codes achieve the information-theoretic optimal trade-off between rate and list size.

arXiv:2202.00240•Feb 1, 2022•2 citations

Comparing the bit-MAP and block-MAP decoding thresholds of reed-muller codes on BMS channels

Shrinivas Kudekar, Santhosh Kumar, Marco Mondelli +2 more

The question whether RM codes are capacity-achieving is a long-standing open problem in coding theory that was recently answered in the affirmative for transmission over erasure channels [1], [2]. Remarkably, the proof does not rely on specific properties of RM codes, apart from their symmetry. Indeed, the main technical result consists in showing that any sequence of linear codes, with doubly-transitive permutation groups, achieves capacity on the memoryless erasure channel under bit-MAP decoding. Thus, a natural question is what happens under block-MAP decoding. In [1], [2], by exploiting further symmetries of the code, the bit-MAP threshold was shown to be sharp enough so that the block erasure probability also converges to 0. However, this technique relies heavily on the fact that the transmission is over an erasure channel. We present an alternative approach to strengthen results regarding the bit-MAP threshold to block-MAP thresholds. This approach is based on a careful analysis of the weight distribution of RM codes. In particular, the flavor of the main result is the following: assume that the bit-MAP error probability decays as N−δ, for some δ > 0. Then, the block-MAP error probability also converges to 0. This technique applies to transmission over any binary memoryless symmetric channel. Thus, it can be thought of as a first step in extending the proof that RM codes are capacity-achieving to the general case.

arXiv:1601.06048•IEEE International Symposium on Information Theory (ISIT)•Jul 1, 2016•28 citations

An Upper Bound on the Error Probability of Rpa Decoding of Reed-Muller Codes Over the Bsc

V. Arvind Rameshwar, V. Lalitha

In this paper, we revisit the Recursive Projection-Aggregation (RPA) decoder, of Ye and Abbe (2020), for Reed-Muller (RM) codes. Our main contribution is an explicit upper bound on the probability of incorrect decoding, using the RPA decoder, over a binary symmetric channel (BSC). Key components of our analysis are explicit estimates of the error probability of maximum likelihood (ML) decoding of first-order RM codes and of the error probabilities during the aggregation phase of the RPA decoder. Importantly, we focus on the events where a single iteration of the RPA decoder, in each recursive call, is sufficient for convergence. Our results allow us to show that for RM codes with blocklength$N=2^{m}$, the RPA decoder can achieve vanishing error probabilities, in the large blocklength limit, for RM orders that grow roughly logarithmically in$m$.

IEEE International Symposium on Information Theory (ISIT)•Jun 22, 2025•2 citations

A lower bound on the probability of error of polar codes over BMS channels

Boaz Shuval, Ido Tal

Consider a polar code designed for some binary memoryless symmetric channel. We develop a lower bound on the probability of error of this polar code under successive-cancellation decoding. The bound exploits the correlation between the various codeword bits and improves upon existing lower bounds.

IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2017•7 citations

Estimates of the bit error probabilities for binary linear block codes and symmetric binary-input memoryless channels

Vladimir B. Balakirsky

•Jan 1, 2002•0 citations

Reed–Muller Codes on CQ Channels via a New Correlation Bound for Quantum Observables

Avijit Mandal, Henry D. Pfister

The question of whether Reed-Muller (RM) codes achieve capacity on binary memoryless symmetric (BMS) channels has drawn attention since it was resolved positively for the binary erasure channel by Kudekar et al. in 2016. In 2021, Reeves and Pfister extended this to prove the bit-error probability vanishes on BMS channels when the code rate is less than capacity. In 2023, Abbe and Sandon improved this to show the block-error probability also goes to zero. These results analyze decoding functions using symmetry and the nested structure of RM codes. In this work, we focus on binary-input symmetric classicalquantum (BSCQ) channels and the Holevo capacity. For a BSCQ, we consider observables that estimate the channel input in the sense of minimizing the mean-squared error (MSE). Using the orthogonal decomposition of these observables under a weighted inner product, we establish a recursive relation for the minimum MSE estimate of a single bit in the RM code. Our results show that any set of$2^{o(\sqrt{\log N})}$bits can be decoded with high probability when the code rate is less than the Holevo capacity.

arXiv:2502.03785•IEEE International Symposium on Information Theory (ISIT)•Jun 22, 2025•1 citation
We strengthen the results from a recent work by the second author, achieving bounds on the weight distribution of binary linear codes that are successful under block-MAP (as well as bit-MAP) decoding on the BEC. We conclude that a linear code that is successful on the BEC can also decode over a range of binary memoryless symmetric (BMS) channels. In particular, applying the result of Kudekar, Kumar, Mondelli, Pfister, Şaşoğlu and Urbanke from STOC 2016, we prove that a Reed–Muller code of positive rate R decodes errors on the p with high probability if p < 1/2 − √2−R(1−2−R).
We present an approach to showing that a linear code is resilient to random errors. We use this approach to obtain decoding results for both transitive codes and Reed-Muller codes. We give three kinds of results about linear codes in general, and transitive linear codes in particular. 1) We give a tight bound on the weight distribution of every transitive linear code C⊆F2NC \subseteq \mathbb{F}_2^NC⊆F2N​: Pr⁡c∈C[∣c∣=αN]≤2−(1−h(α))dim(C)\Pr_{c \in C}[|c| = αN] \leq 2^{-(1-h(α)) \mathsf{dim}(C)}Prc∈C​[∣c∣=αN]≤2−(1−h(α))dim(C). 2) We give a criterion that certifies that a linear code CCC can be decoded on the binary symmetric channel. Let Ks(x)K_s(x)Ks​(x) denote the Krawtchouk polynomial of degree sss, and let C⊥C^\perpC⊥ denote the dual code of CCC. We show that bounds on Ec∈C⊥[KεN(∣c∣)2]\mathbb{E}_{c \in C^{\perp}}[ K_{εN}(|c|)^2]Ec∈C⊥​[KεN​(∣c∣)2] imply that CCC recovers from errors on the binary symmetric channel with parameter εεε. Weaker bounds can be used to obtain list-decoding results using similar methods. One consequence of our criterion is that whenever the weight distribution of C⊥C^\perpC⊥ is sufficiently close to the binomial distribution in some interval around N2\frac{N}{2}2N​, CCC is resilient to εεε-errors. 3) We combine known estimates for the Krawtchouk polynomials with our weight bound for transitive codes, and with known weight bounds for Reed-Muller codes, to obtain list-decoding results for both these families of codes. In some regimes, our bounds for Reed-Muller codes achieve the information-theoretic optimal trade-off between rate and list size.
The question whether RM codes are capacity-achieving is a long-standing open problem in coding theory that was recently answered in the affirmative for transmission over erasure channels [1], [2]. Remarkably, the proof does not rely on specific properties of RM codes, apart from their symmetry. Indeed, the main technical result consists in showing that any sequence of linear codes, with doubly-transitive permutation groups, achieves capacity on the memoryless erasure channel under bit-MAP decoding. Thus, a natural question is what happens under block-MAP decoding. In [1], [2], by exploiting further symmetries of the code, the bit-MAP threshold was shown to be sharp enough so that the block erasure probability also converges to 0. However, this technique relies heavily on the fact that the transmission is over an erasure channel. We present an alternative approach to strengthen results regarding the bit-MAP threshold to block-MAP thresholds. This approach is based on a careful analysis of the weight distribution of RM codes. In particular, the flavor of the main result is the following: assume that the bit-MAP error probability decays as N−δ, for some δ > 0. Then, the block-MAP error probability also converges to 0. This technique applies to transmission over any binary memoryless symmetric channel. Thus, it can be thought of as a first step in extending the proof that RM codes are capacity-achieving to the general case.
In this paper, we revisit the Recursive Projection-Aggregation (RPA) decoder, of Ye and Abbe (2020), for Reed-Muller (RM) codes. Our main contribution is an explicit upper bound on the probability of incorrect decoding, using the RPA decoder, over a binary symmetric channel (BSC). Key components of our analysis are explicit estimates of the error probability of maximum likelihood (ML) decoding of first-order RM codes and of the error probabilities during the aggregation phase of the RPA decoder. Importantly, we focus on the events where a single iteration of the RPA decoder, in each recursive call, is sufficient for convergence. Our results allow us to show that for RM codes with blocklengthN=2mN=2^{m}N=2m, the RPA decoder can achieve vanishing error probabilities, in the large blocklength limit, for RM orders that grow roughly logarithmically inmmm.
The question of whether Reed-Muller (RM) codes achieve capacity on binary memoryless symmetric (BMS) channels has drawn attention since it was resolved positively for the binary erasure channel by Kudekar et al. in 2016. In 2021, Reeves and Pfister extended this to prove the bit-error probability vanishes on BMS channels when the code rate is less than capacity. In 2023, Abbe and Sandon improved this to show the block-error probability also goes to zero. These results analyze decoding functions using symmetry and the nested structure of RM codes. In this work, we focus on binary-input symmetric classicalquantum (BSCQ) channels and the Holevo capacity. For a BSCQ, we consider observables that estimate the channel input in the sense of minimizing the mean-squared error (MSE). Using the orthogonal decomposition of these observables under a weighted inner product, we establish a recursive relation for the minimum MSE estimate of a single bit in the RM code. Our results show that any set of2o(log⁡N)2^{o(\sqrt{\log N})}2o(logN​)bits can be decoded with high probability when the code rate is less than the Holevo capacity.