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:2604.02994

Weight distribution bounds to relate minimum distance, list decoding, and symmetric channel performance

Donald Kougang-Yombi, Jan Hązła

Published Apr 3, 2026• 0 citations
arXivHTMLPDF

Abstract

We study relationships between worst-case and random-noise properties of error correcting codes. More concretely, we consider connections between minimum distance, list decoding radius, and block error probability on noisy channels. A recent result of Pernice, Sprumont, and Wootters established the tight connection between list decoding radius and symmetric channel performance for linear codes. We extend this result to general codes. The proof proceeds by directly bounding the weight distribution rather than by sharp threshold techniques. We then turn to the relation between minimum distance and symmetric channel performance. The results we just described imply that a $q$-ary code of relative distance $δ$ has vanishing error probability on the symmetric channel up to the Johnson radius $J_q(δ)$. We improve upon this bound in the case of linear codes, for a range $δ$, for $q\ge 4$. In our proof we consider the \emph{erasure} properties of codes, and bound their weight distribution through inequalities introduced by Samorodnitsky. The latter part of the proof gives a more general technique that bounds the symmetric channel performance of a linear code with constant relative distance and good erasure channel performance.

DOI
10.48550/arxiv.2604.02994

Related papers

Weighted-Hamming Metric for Parallel Channels

Sebastian Bitzer, Alberto Ravagnani, Violetta Weger

Independent parallel q-ary symmetric channels are a suitable transmission model for several applications. The weighted-Hamming metric is tailored to this setting and enables optimal decoding performance. We show that some weighted-Hamming-metric codes exhibit the unusual property that all errors beyond half the minimum distance can be corrected. Nevertheless, a tight relation between the error-correction capability of a code and its minimum distance can be established. Generalizing their Hamming-metric counterparts, upper and lower bounds on the cardinality of a code with a given weighted-Hamming distance are obtained. Finally, we propose a simple code construction with optimal minimum distance for specific parameters.

arXiv:2401.17801•IEEE International Symposium on Information Theory (ISIT)•Jul 7, 2024•1 citation

A criterion for decoding on the binary symmetric channel

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 and doubly transitive 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 $:$ \mathop {\Pr }\limits_{c \in C}[ \text{wt}(c) = \alpha N] \leq 2^{-(1-h(\alpha)) \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_{\epsilon N}( \text{wt}(c))^2] $ imply that $ C $ recovers from errors on the binary symmetric channel with parameter $ \epsilon $. 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 $ \epsilon $-errors.3. We combine known estimates for the Krawtchouk polynomials with our weight bound for transitive codes, and with known weight bounds for doubly transitive codes, to obtain list-decoding results for both these families of codes. In some regimes, our bounds for doubly transitive codes achieve the information-theoretic optimal trade-off between rate and list size.

Advances in Mathematics of Communications•Feb 28, 2024•2 citations

The list decoding error probability of linear codes over the erasure channel

Linzhi Shen, Fang‐Wei Fu

In this paper, we study the list decoding error probability of a linear code over the erasure channel. The notion of L-incorrigible sets of a linear code is introduced to characterize its performance under list decoding. The L-incorrigible set distribution of a linear code can also be used to completely determine its decoding error probability under maximum likelihood decoding over the erasure channel. Furthermore, we show that the L-incorrigible set distribution of a linear code can be determined by its support weight distribution. Finally, the error exponent of the unsuccessful decoding probability under optimal decoding for the ensemble of all [n, nR] linear codes is determined.

IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2015•1 citation

From Bit to Block: Decoding on Erasure Channels

Henry D. Pfister, Oscar Sprumont, Gilles Zémor

We provide a general framework for bounding the block error threshold of a linear code$C \subseteq \mathbb{F}_{2}^{N}$over the erasure channel in terms of its bit error threshold. Our approach relies on understanding the minimum support weight of any$r$-dimensional subcode of$C$, for all small values of$r$. As a proof of concept, we use our machinery to obtain a new proof of the celebrated result that Reed-Muller codes achieve capacity on the erasure channel with respect to block error probability.

arXiv:2501.05748•IEEE International Symposium on Information Theory (ISIT)•Jun 22, 2025•0 citations

Structural Conditions for Performance Guarantees in Coding Theory and Learning

Donald Kougang Yombi, Justus Liebig University Giessen

This dissertation investigates how structural properties of information-processing systems govern their performance in communication and learning tasks. In the first part, we develop new tools in coding and information theory. We study channel comparison problems and introduce a quantitative refinement of the classical notion of \emph{more capable} channels, termed \emph{more capable with advantage}. We prove tensorization properties, characterize the comparison between the binary symmetric channel (BSC) and binary erasure channel (BEC), and apply the framework to obtain new list-decoding guarantees and improved lower bounds on the entropy rate of binary hidden Markov processes. Then, we investigate the relationship between worst-case and random-noise properties of error-correcting codes. In particular, we establish new connections between minimum distance, list-decoding radius, weight distributions, and performance on symmetric channels. Our results extend recent characterizations of the interplay between list decoding capacity and channel capacity from linear codes to arbitrary codes, and provide improved bounds for linear codes through the analysis of erasure-channel behavior and Samorodnitsky's inequalities. The second part of the dissertation examines analogous questions in learning theory through the lens of neural networks. We study the learnability of high-degree parity functions, a classical benchmark for understanding the computational limits of learning algorithms. We show that for gradient descent on regular neural networks, learnability depends critically on the initial distribution of the parameters. While discrete Rademacher initialization enables efficient learning of almost-full parities, sufficiently large Gaussian perturbations prevent learning. These results reveal a sharp dependence of optimization dynamics on initialization. The analysis introduces gradient-alignment (GAL), a loss-dependent measure, that quantifies how the choice of initialization could affects the learnability of a target function. Taken together, the results of this dissertation demonstrate that quantitative structural information—whether encoded in channel orderings, code weight distributions, or neural-network initializations—can fundamentally determine the boundary between success and failure in information processing tasks.

•Jan 1, 2026•0 citations

Bounds on Maximum Likelihood Decoding Performance for Linear Codes at Low Rates

Hideki Yagi, H. Vincent Poor

For a given linear code (ensemble), upper bounds on the error probability under maximum likelihood decoding are investigated at low rates. A class of symmetric memoryless channels suitable for Bhattacharyya-type bounds, which are particularly of importance at low rates, is introduced. Over a symmetric channel, a lower bound on the error exponent is derived for a given linear code. A sufficient condition for achieving the expurgated exponent, which is the best among known error exponents at low rates, within a fixed discrepancy is given. Over a general discrete memoryless channel, the same analysis provides a lower bound on the average error exponent for an ensemble of coset codes generated by a given linear code. The bounding technique is extended to the case of generalized maximum likelihood decoding with erasure and list- decoding options.

IEEE Transactions on Information Theory•Mar 12, 2013•2 citations
We study relationships between worst-case and random-noise properties of error correcting codes. More concretely, we consider connections between minimum distance, list decoding radius, and block error probability on noisy channels. A recent result of Pernice, Sprumont, and Wootters established the tight connection between list decoding radius and symmetric channel performance for linear codes. We extend this result to general codes. The proof proceeds by directly bounding the weight distribution rather than by sharp threshold techniques. We then turn to the relation between minimum distance and symmetric channel performance. The results we just described imply that a qqq-ary code of relative distance δδδ has vanishing error probability on the symmetric channel up to the Johnson radius Jq(δ)J_q(δ)Jq​(δ). We improve upon this bound in the case of linear codes, for a range δδδ, for q≥4q\ge 4q≥4. In our proof we consider the \emph{erasure} properties of codes, and bound their weight distribution through inequalities introduced by Samorodnitsky. The latter part of the proof gives a more general technique that bounds the symmetric channel performance of a linear code with constant relative distance and good erasure channel performance.
Independent parallel q-ary symmetric channels are a suitable transmission model for several applications. The weighted-Hamming metric is tailored to this setting and enables optimal decoding performance. We show that some weighted-Hamming-metric codes exhibit the unusual property that all errors beyond half the minimum distance can be corrected. Nevertheless, a tight relation between the error-correction capability of a code and its minimum distance can be established. Generalizing their Hamming-metric counterparts, upper and lower bounds on the cardinality of a code with a given weighted-Hamming distance are obtained. Finally, we propose a simple code construction with optimal minimum distance for specific parameters.
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 and doubly transitive 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 ::: \mathop {\Pr }\limits_{c \in C}[ \text{wt}(c) = \alpha N] \leq 2^{-(1-h(\alpha)) \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_{\epsilon N}( \text{wt}(c))^2] $ imply that $ C $ recovers from errors on the binary symmetric channel with parameter $ \epsilon $. 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 $ \epsilon $-errors.3. We combine known estimates for the Krawtchouk polynomials with our weight bound for transitive codes, and with known weight bounds for doubly transitive codes, to obtain list-decoding results for both these families of codes. In some regimes, our bounds for doubly transitive codes achieve the information-theoretic optimal trade-off between rate and list size.
In this paper, we study the list decoding error probability of a linear code over the erasure channel. The notion of L-incorrigible sets of a linear code is introduced to characterize its performance under list decoding. The L-incorrigible set distribution of a linear code can also be used to completely determine its decoding error probability under maximum likelihood decoding over the erasure channel. Furthermore, we show that the L-incorrigible set distribution of a linear code can be determined by its support weight distribution. Finally, the error exponent of the unsuccessful decoding probability under optimal decoding for the ensemble of all [n, nR] linear codes is determined.
We provide a general framework for bounding the block error threshold of a linear codeC⊆F2NC \subseteq \mathbb{F}_{2}^{N}C⊆F2N​over the erasure channel in terms of its bit error threshold. Our approach relies on understanding the minimum support weight of anyrrr-dimensional subcode ofCCC, for all small values ofrrr. As a proof of concept, we use our machinery to obtain a new proof of the celebrated result that Reed-Muller codes achieve capacity on the erasure channel with respect to block error probability.
This dissertation investigates how structural properties of information-processing systems govern their performance in communication and learning tasks. In the first part, we develop new tools in coding and information theory. We study channel comparison problems and introduce a quantitative refinement of the classical notion of \emph{more capable} channels, termed \emph{more capable with advantage}. We prove tensorization properties, characterize the comparison between the binary symmetric channel (BSC) and binary erasure channel (BEC), and apply the framework to obtain new list-decoding guarantees and improved lower bounds on the entropy rate of binary hidden Markov processes. Then, we investigate the relationship between worst-case and random-noise properties of error-correcting codes. In particular, we establish new connections between minimum distance, list-decoding radius, weight distributions, and performance on symmetric channels. Our results extend recent characterizations of the interplay between list decoding capacity and channel capacity from linear codes to arbitrary codes, and provide improved bounds for linear codes through the analysis of erasure-channel behavior and Samorodnitsky's inequalities. The second part of the dissertation examines analogous questions in learning theory through the lens of neural networks. We study the learnability of high-degree parity functions, a classical benchmark for understanding the computational limits of learning algorithms. We show that for gradient descent on regular neural networks, learnability depends critically on the initial distribution of the parameters. While discrete Rademacher initialization enables efficient learning of almost-full parities, sufficiently large Gaussian perturbations prevent learning. These results reveal a sharp dependence of optimization dynamics on initialization. The analysis introduces gradient-alignment (GAL), a loss-dependent measure, that quantifies how the choice of initialization could affects the learnability of a target function. Taken together, the results of this dissertation demonstrate that quantitative structural information—whether encoded in channel orderings, code weight distributions, or neural-network initializations—can fundamentally determine the boundary between success and failure in information processing tasks.
For a given linear code (ensemble), upper bounds on the error probability under maximum likelihood decoding are investigated at low rates. A class of symmetric memoryless channels suitable for Bhattacharyya-type bounds, which are particularly of importance at low rates, is introduced. Over a symmetric channel, a lower bound on the error exponent is derived for a given linear code. A sufficient condition for achieving the expurgated exponent, which is the best among known error exponents at low rates, within a fixed discrepancy is given. Over a general discrete memoryless channel, the same analysis provides a lower bound on the average error exponent for an ensemble of coset codes generated by a given linear code. The bounding technique is extended to the case of generalized maximum likelihood decoding with erasure and list- decoding options.