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

arXiv:2505.00974 · IEEE International Symposium on Information Theory (ISIT)

On the Worst-Case Complexity of Gibbs Decoding for Reed-Muller Codes

Xuzhe Xia, Nicholas Kwan, Lele Wang

Published Jun 22, 2025• 0 citations
arXivHTMLPDF

Abstract

Reed-Muller (RM) codes are known to achieve capacity on binary symmetric channels (BSC) under the Maximum a Posteriori (MAP) decoder. However, it remains an open problem to design a capacity achieving polynomial-time RM decoder. Due to a lemma by Liu, Cuff, and Verdú, it can be shown that decoding by sampling from the posterior distribution is also capacity-achieving for RM codes over BSC. The Gibbs decoder is one such Markov Chain Monte Carlo (MCMC) based method, which samples from the posterior distribution by flipping message bits according to the posterior, and can be modified to give other MCMC decoding methods. In this paper, we analyze the mixing time of the Gibbs decoder for RM codes. Our analysis reveals that the Gibbs decoder can exhibit slow mixing for certain carefully constructed sequences. This slow mixing implies that, in the worst-case scenario, the decoder requires super-polynomial time to converge to the desired posterior distribution.

DOI
10.1109/isit63088.2025.11195291

Related papers

On polylogarithmic decoding complexity for reed-muller codes

Ilya I. Dumer

For Reed-Muller (RM) codes of length n and distance d, a recursive decoding algorithm is designed that has complexity of order nlogn for any fixed rate R, and corrects most error patterns of weight up to (dlnd)/2 on the binary symmetric channels (BSC) and up to (2dlnd)/pi on the AWGN channels. For long RM codes of fixed order r, a vanishing decoding error probability and polylogarithmic decoding complexity of order (logn)r+1are obtained on the BSC given any transition probability p that is bounded away from 1/2

IEEE International Symposium on Information Theory (ISIT)•Dec 23, 2004•1 citation

Efficient Maximum-Likelihood Decoding of Reed–Muller RM(m−3,m) Codes

Andrew Thangaraj, Henry D. Pfister

Reed-Muller (RM) codes, a classical family of codes known for their elegant algebraic structure, have recently been shown to achieve capacity under maximum-likelihood (ML) decoding on the binary erasure channel and this has rekindled interest in their efficient decoding. We consider the code family RM(m-3,m) and develop a new ML decoder, for transmission over the binary symmetric channel, that exploits their large symmetry group. The new decoder has lower complexity than an earlier method introduced by Seroussi and Lempel in 1983.

IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2020•5 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

An Analysis 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). Importantly, we focus on the events where a \emph{single} iteration of the RPA decoder, in each recursive call, is sufficient for convergence. Key components of our analysis are explicit estimates of the probability of incorrect decoding of first-order RM codes using a maximum likelihood (ML) decoder, and estimates of the error probabilities during the aggregation phase of the RPA decoder. 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$.

arXiv:2412.08129•Dec 11, 2024•2 citations

Decoding of Reed-Muller codes with polylogarithmic complexity

Ilya I. Dumer

Code transmission is considered over a binary symmetric (BS) channel whose bit error probability is arbitrarily close to 1/2. New recursive decoding algorithms are designed for Reed-Muller (RM) codes of growing length 2m and fixed order r. The algorithms retrieve all information with a vanishing error probability and polylogarithmic complexity of order mr+1.

•Jan 5, 2004•2 citations

On recursive decoding with sublinear complexity for Reed-Muller codes

Ilya I. Dumer

Reed-Muller (RM) codes (m, r) of length 2/sup m/ are considered on a binary symmetric (BS) channel with high crossover error probability 1/2 -/spl epsiv/. For an arbitrarily small /spl epsiv/>0, new recursive decoding algorithms are designed that retrieve all information bits of RM codes of fixed order r with a vanishing error probability and sublinear complexity of order O(m/sup r+1/). The algorithms utilize a vanishing fraction of the received symbols for both hard- and soft-decision decoding.

IEEE Information Theory Workshop (ITW)•Mar 1, 2004•2 citations
Reed-Muller (RM) codes are known to achieve capacity on binary symmetric channels (BSC) under the Maximum a Posteriori (MAP) decoder. However, it remains an open problem to design a capacity achieving polynomial-time RM decoder. Due to a lemma by Liu, Cuff, and Verdú, it can be shown that decoding by sampling from the posterior distribution is also capacity-achieving for RM codes over BSC. The Gibbs decoder is one such Markov Chain Monte Carlo (MCMC) based method, which samples from the posterior distribution by flipping message bits according to the posterior, and can be modified to give other MCMC decoding methods. In this paper, we analyze the mixing time of the Gibbs decoder for RM codes. Our analysis reveals that the Gibbs decoder can exhibit slow mixing for certain carefully constructed sequences. This slow mixing implies that, in the worst-case scenario, the decoder requires super-polynomial time to converge to the desired posterior distribution.
For Reed-Muller (RM) codes of length n and distance d, a recursive decoding algorithm is designed that has complexity of order nlogn for any fixed rate R, and corrects most error patterns of weight up to (dlnd)/2 on the binary symmetric channels (BSC) and up to (2dlnd)/pi on the AWGN channels. For long RM codes of fixed order r, a vanishing decoding error probability and polylogarithmic decoding complexity of order (logn)r+1are obtained on the BSC given any transition probability p that is bounded away from 1/2
Reed-Muller (RM) codes, a classical family of codes known for their elegant algebraic structure, have recently been shown to achieve capacity under maximum-likelihood (ML) decoding on the binary erasure channel and this has rekindled interest in their efficient decoding. We consider the code family RM(m-3,m) and develop a new ML decoder, for transmission over the binary symmetric channel, that exploits their large symmetry group. The new decoder has lower complexity than an earlier method introduced by Seroussi and Lempel in 1983.
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.
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). Importantly, we focus on the events where a \emph{single} iteration of the RPA decoder, in each recursive call, is sufficient for convergence. Key components of our analysis are explicit estimates of the probability of incorrect decoding of first-order RM codes using a maximum likelihood (ML) decoder, and estimates of the error probabilities during the aggregation phase of the RPA decoder. Our results allow us to show that for RM codes with blocklength N=2mN = 2^mN=2m, the RPA decoder can achieve vanishing error probabilities, in the large blocklength limit, for RM orders that grow roughly logarithmically in mmm.
Reed-Muller (RM) codes (m, r) of length 2/sup m/ are considered on a binary symmetric (BS) channel with high crossover error probability 1/2 -/spl epsiv/. For an arbitrarily small /spl epsiv/>0, new recursive decoding algorithms are designed that retrieve all information bits of RM codes of fixed order r with a vanishing error probability and sublinear complexity of order O(m/sup r+1/). The algorithms utilize a vanishing fraction of the received symbols for both hard- and soft-decision decoding.