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.

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$.

In this paper, we consider a recent channel model of a nanopore sequencer proposed by McBain, Viterbo, and Saunderson (2024), termed the noisy nanopore channel (NNC). In essence, an NNC is a noisy duplication channel, whose input source has a specific Markov structure. We present computable lower and upper bounds on the channel capacity of selected NNCs, via simple information-theoretic inequalities. In particular, we provide a (tight) lower bound on the capacity of the noiseless NNC. We then consider the setting where the memory of the input process is large and the random noise introduces erasures. We demonstrate that for such an NNC, it is possible to achieve information rates close to the noise-free capacity, using simple encoding and decoding schemes.

This paper develops an algorithmic approach for obtaining estimates of the weight enumerators of Reed-Muller (RM) codes. Our algorithm is based on a technique for estimating the partition functions of spin systems, which in turn employs a sampler that produces codewords according to a suitably defined Gibbs distribution. We apply our method to moderate-blocklength RM RM) codes. Our algorithm is based on a technique for estimating the partition functions of spin systems, which in turn employs a sampler that produces codewords according to a suitably defined Gibbs distribution. We apply our method to moderate-blocklength RM codes and derive approximate values of their weight enumerators. We observe that the rates of the weight enumerator estimates returned by our method are close to the true rates when these rates are either known or computable by brute-force search; in other cases, our computations provide provably robust estimates. As a by-product, our sampling algorithm also allows us to put together the weight spectrum, i.e., the weights at which the enumerators are non-zero, of an RM code, by providing witnesses in the form of codewords at each weight in the spectrum. We illustrate our method by providing estimates of the hitherto unknown weight enumerators of the RM(11, 5) code for weights that are multiples of 4 between 512 and 1024. We also obtain the exact weight spectrum of the RM(10, 4) code.

We investigate the fundamental limits of reliable communication over multi-view channels, in which the channel output is comprised of a large number of independent noisy views of a transmitted symbol. We consider first the setting of multi-view discrete memoryless channels and then extend our results to general multi-view channels (using multi-letter formulas). We argue that the channel capacity and dispersion of such multi-view channels converge exponentially fast in the number of views to the entropy and varentropy of the input distribution, respectively. We identify the exact rate of convergence as the smallest Chernoff information between two conditional distributions of the output, conditioned on unequal inputs. For the special case of the deletion channel, we compute upper bounds on this Chernoff information. Finally, we present a new channel model we term the Poisson approximation channel — of possible independent interest — whose capacity closely approximates the capacity of the multi-view binary symmetric channel for any fixed number of views.

This paper develops an algorithmic approach for obtaining estimates of the weight enumerators of Reed-Muller (RM) codes. Our algorithm is based on a technique for estimating the partition functions of spin systems, which in turn employs a sampler that produces codewords according to a suitably defined Gibbs distribution. We apply our method to moderate-blocklength RM codes and derive approximate values of their weight enumerators. We observe that the rates of the weight enumerator estimates returned by our method are close to the true rates when these rates are either known or computable by brute-force search; in other cases, our computations provide provably robust estimates. As a byproduct, our sampling algorithm also allows us to obtain estimates of the weight spectra of RM codes. We illustrate our methods by providing estimates of the hitherto unknown weight enumerators of the RM(11,5) code and the exact weight spectra of the RM(10, 3) and RM(10, 4) codes.

In this paper, we investigate the fundamental limits of reliable communication over a discrete memoryless channel (DMC) when there are a large number of noisy views of a transmitted symbol, i.e., when several copies of a single symbol are sent independently through the DMC. We argue that the channel capacity and dispersion of such a multi-view DMC converge exponentially quickly in the number of views to to the entropy and varentropy of the input distribution, respectively, and identify the exact rate of convergence. This rate equals the smallest Chernoff information between two conditional distributions of the output given unequal inputs. Our results hence help us characterize the largest finite-blocklength rates achievable for any fixed error probability. We also present a new channel model that we call the Poisson approximation channel-of possible independent interest-whose capacity closely approximates the capacity of the multi-view binary symmetric channel (BSC).

We analyze noisy binary sequence reconstruction subject to exactly$t$distinct substitution errors, where a fixed number of distinct noisy output sequences (or views) are available at the decoder. The error sequences are assumed to be drawn uniformly at random, without replacement, from the Hamming sphere of radius$t-\mathbf{a}$natural extension of the adversarial error model considered in the classical work of Levenshtein (2001). In this paper, we fix the decoder to be the majority-vote decoder, which was proved in Levenshtein (2001) to be capable of reconstructing any sequence in the “worst-case,” subject to the presence of at least a certain number of views$N_{\mathbf{wc}}$. Such a decoder is “optimal in the worst-case” in that when the number of views is smaller than$N_{\mathbf{wc}}$, there exists a sequence that cannot be reconstructed by any decoder. Via a correspondence with a counting problem in the space of binary matrices, we first provide a simple Monte-Carlo method for estimating the probability$P_{\mathbf{Maj}}$of successful decoding, using the majority-vote decoder. Next, via the same correspondence, we present an analytical lower bound on$P_{\mathbf{Maj}}$, which is derived using a recursive procedure. These results then allow us to bound the expected number of views required for reconstruction.

In this paper, we present numerical upper bounds on the sizes of constrained codes with a prescribed minimum distance. We accomplish this by extending Delsarte's linear program (LP) (Delsarte (1973)) to the setting of constrained codes, with the value of optimal solutions to this LP giving us the desired upper bound, for a fixed constraint. We also describe an equivalent LP, with fewer variables and LP constraints, obtained by symmetrizing our LP. We observe that for different constraints of interest, our upper bounds beat the generalized sphere packing upper bounds of Fazeli, Vardy, and Yaakobi (2015).

In this paper, we consider the problem of computing the sizes of subcodes of binary linear codes, all of whose codewords need to satisfy an additional property, which we call a constraint. Using a simple identity from the Fourier analysis of Boolean functions, we transform our counting problem into a question about the structure of the dual code. We illustrate the utility of our method in providing explicit values or numerical algorithms for our counting problem, from the somewhat surprising observation that for different constraints of interest, the Fourier transform of the indicator function of the constraint is efficiently computable.

The paper considers coding schemes derived from Reed-Muller (RM) codes, for transmission over input-constrained memoryless channels. Our focus is on the$(d,\infty)$-runlength limited (RLL) constraint, which mandates that any pair of successive 1s be separated by at least$d~0\text{s}$. In our study, we first consider$(d,\infty)$-RLL subcodes of RM codes, taking the coordinates of the RM codes to be in the standard lexicographic ordering. We show, via a simple construction, that RM codes of rate$R$have linear$(d,\infty)$-RLL subcodes of rate$R\cdot {2^{-\left \lceil{ \log _{2}(d+1)}\right \rceil }}$. We then show that our construction is essentially rate-optimal, by deriving an upper bound on the rates of linear$(d,\infty)$-RLL subcodes of RM codes of rate$R$. Next, for the special case when$d=1$, we prove the existence of potentially non-linear$(1,\infty)$-RLL subcodes that achieve a rate of$\max \left ({0,R-\frac {3}8}\right)$. This, for$R > 3/4$, beats the$R/2$rate obtainable from linear subcodes. We further derive upper bounds on the rates of$(1,\infty)$-RLL subcodes, not necessarily linear, of a certain canonical sequence of RM codes of rate$R$. We then shift our attention to settings where the coordinates of the RM code are not ordered according to the lexicographic ordering, and derive rate upper bounds for linear$(d,\infty)$-RLL subcodes in these cases as well. Finally, we present a new two-stage constrained coding scheme, again using RM codes of rate$R$, which outperforms any linear coding scheme using$(d,\infty)$-RLL subcodes, for values of$R$close to 1.

This paper considers the input-constrained binary memoryless symmetric (BMS) channel, without feedback. The channel input sequence respects the (d, ∞)-runlength limited (RLL) constraint, which mandates that any pair of successive 1s be separated by at least d 0s. We consider the problem of designing explicit codes for such channels. In particular, we work with the Reed-Muller (RM) family of codes, which were shown by Reeves and Pfister (2021) to achieve the capacity of any unconstrained BMS channel, under bit-MAP decoding. We show that it is possible to pick (d, ∞)-RLL subcodes of a capacity-achieving (over the unconstrained BMS channel) sequence of RM codes such that the subcodes achieve, under bit-MAP decoding, rates of $C \cdot {2^{ - \left\lceil {{{\log }_2}(d + 1)} \right\rceil }}$, where C is the capacity of the BMS channel. Finally, we also introduce techniques for upper bounding the rate of any (1, ∞)-RLL subcode of a specific capacity-achieving sequence of RM codes.

In this work, we address the question of the largest rate of linear subcodes of Reed-Muller (RM) codes, all of whose codewords respect a runlength-limited (RLL) constraint. Our interest is in the (d, ∞)-RLL constraint, which mandates that every pair of successive 1s be separated by at least d 0s. Consider any sequence ${\left\{ {{\mathcal{C}_m}} \right\}_{m \geq 1}}$ of RM codes with increasing blocklength, whose rates approach R, in the limit as the blocklength goes to infinity. We show that for any linear (d, ∞)-RLL subcode, ${\hat {\mathcal{C}}_m}$, of the code ${\mathcal{C}_m}$, it holds that the rate of ${\hat {\mathcal{C}}_m}$ is at most $\frac{R}{{d + 1}}$, in the limit as the blocklength goes to infinity. We also consider scenarios where the coordinates of the RM codes are not ordered according to the standard lexicographic ordering, and derive rate upper bounds for linear (d, ∞)-RLL subcodes, in those cases as well. Next, for the setting of a (d, ∞)-RLL input-constrained binary memoryless symmetric (BMS) channel, we devise a new coding scheme, based on cosets of RM codes. Again, in the limit of blocklength going to infinity, this code outperforms any linear subcode of an RM code, in terms of rate, for low noise regimes of the channel.

The paper considers the input-constrained binary erasure channel (BEC) with causal, noiseless feedback. The channel input sequence respects the ($d, \infty$)-runlength limited (RLL) constraint, i.e., any pair of successive 1s must be separated by at least$d$0s. We derive upper and lower bounds on the feedback capacity of this channel, given by single parameter maximization problems that differ exclusively in the domain of maximization. The results of Sabag et al. (2016) show that our bounds are tight for the case when$d=1$. For the case when$d=2$, our lower bound implies that the feedback capacity is equal to the capacity with non-causal knowledge of erasures, for$\epsilon\in [0,1-\frac{1}{2\log_{2}(3/2)}]$. The approach in this paper follows Sabag et al. (2017), by deriving single-letter bounds on the feedback capacity, based on output distributions supported on a finite$Q$-graph, which is a directed graph with edges labelled by output symbols.

This paper studies the capacities of input-driven finite-state channels, i.e., channels whose current state is a time-invariant deterministic function of the previous state and the current input. We lower bound the capacity of such a channel using a dynamic programming formulation of a bound on the maximum reverse directed information rate. We show that the dynamic programming-based bounds can be simplified by solving the corresponding Bellman equation explicitly. In particular, we provide analytical lower bounds on the capacities of (d, k)-runlength-limited input-constrained binary symmetric and binary erasure channels.