We analyze the performance of the Recursive Projection-Aggregation (RPA) decoder of Ye and Abbe (2020), for Reed-Muller (RM) codes, over general binary memoryless symmetric (BMS) channels. Our work is a significant generalization of a recent result of Rameshwar and Lalitha (2025) that showed that the RPA decoder provably achieves vanishing error probabilities for "low-rate" RM codes, over the binary symmetric channel (BSC). While a straightforward generalization of the proof strategy in that paper will require additional, restrictive assumptions on the BMS channel, our technique, which employs an equivalence between the RPA projection operation and a part of the "channel combining" phase in polar codes, requires no such assumptions. Interestingly, such an equivalence allows for the use of a generic union bound on the error probability of the first-order RM code (the "base case" of the RPA decoder), under maximum-likelihood decoding, which holds for any BMS channel. We then exploit these observations in the proof strategy outlined in the work of Rameshwar and Lalitha (2025), and argue that, much like in the case of the BSC, one can obtain vanishing error probabilities, in the large $n$ limit (where $n$ is the blocklength), for RM orders that scale roughly as $\log \log n$, for all BMS channels.

Robust Gray codes were introduced by (Lolck and Pagh, SODA 2024). Informally, a robust Gray code is a (binary) Gray code$\mathcal {G}$so that, given a noisy version of the encoding$\mathcal {G}(j)$of an integer j, one can recover$\hat {j}$that is close to j (with high probability over the noise). Such codes have found applications in differential privacy. In this work, we present near-optimal constructions of robust Gray codes. In more detail, we construct a Gray code$\mathcal {G}$of rate$1 - H_{2}(p) - \varepsilon $that is efficiently encodable, and that is robust in the following sense. Supposed that$\mathcal {G}(j)$is passed through the binary symmetric channel${\text {BSC}}_{p}$with cross-over probability p, to obtain x. We present an efficient decoding algorithm that, given x, returns an estimate$\hat {j}$so that$| j - \hat {j}|$is small with high probability.

A robust Gray code, formally introduced by (Lolck and Pagh, SODA 2024), is a Gray code that additionally has the property that, given a noisy version of the encoding of an integer$j$, it is possible to reconstruct$\hat{j}$so that$\vert j-\hat{j}\vert$is small with high probability. That work presented a transformation that transforms a binary code$\mathcal{C}$of rate$R$to a robust Gray code with rate$\Omega(R)$, where the constant in the$\Omega(\cdot)$can be at most 1/4. We improve upon their construction by presenting a transformation from a (linear) binary code$\mathcal{C}$to a robust Gray code with similar robustness guarantees, but with rate that can approach$R/2$. A full version of this paper can be found in [1].

We consider the problem of coded distributed computing using polar codes. The average execution time of a coded computing system is related to the error probability for transmission over the binary erasure channel in recent work by Soleymani, Jamali and Mahdavifar, where the performance of binary linear codes is investigated. In this paper, we focus on polar codes and unveil a connection between the average execution time and the scaling exponent μ of the family of codes. In the finite-length characterization of polar codes, the scaling exponent is a key object capturing the speed of convergence to capacity. In particular, we show that (i) the gap between the normalized average execution time of polar codes and that of optimal MDS codes is O(n–1/μ), and (ii) this upper bound can be improved to roughly O(n–1/2) by considering polar codes with large kernels. We conjecture that these bounds could be improved to O(n–2/μ) and O(n–1), respectively, and provide a heuristic argument as well as numerical evidence supporting this view.

Reed-Muller (RM) codes are one of the oldest families of codes. Recently, a recursive projection aggregation (RPA) decoder has been proposed, which achieves a performance that is close to the maximum likelihood decoder for short-length RM codes. One of its main drawbacks, however, is the large amount of computations needed. In this paper, we devise a new algorithm to lower the computational budget while keeping a performance close to that of the RPA decoder. The proposed approach consists of multiple sparse RPAs that are generated by performing only a selection of projections in each sparsified decoder. In the end, a cyclic redundancy check (CRC) is used to decide between output codewords. Simulation results show that our proposed approach reduces the RPA decoder's computations by up to 80% with negligible performance loss.