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

IEEE International Symposium on Information Theory (ISIT)

About the reliability function of symmetric channel under list decoding

Vladimir M. Blinovsky

Published Jul 1, 2011• 0 citations
Publisher

Abstract

We complete the derivation of the formula for the reliability function of q-ary symmetric channel under list decoding for zero rate.
DOI
10.1109/isit.2011.6034204

Related papers

Remark on the reliability function of a symmetric channel under list decoding

Vladimir M. Blinovsky

We complete the derivation of a formula for the reliability function of a q -ary symmetric channel under list decoding at zero rate.

Problems of Information Transmission•Jun 1, 2011•0 citations

Zero-rate Reliability Function for Mismatched Decoding

Marco Bondaschi, Albert Guillén i Fàbregas, Marco Dalai

We derive an upper bound on the reliability function of mismatched decoding for zero-rate codes. The bound is based on a result by Komlós that shows the existence of a subcode with certain symmetry properties. The bound is shown to coincide with the expurgated exponent at rate zero for a broad family of channel and decoding metric pairs. A full version of this paper is accessible at: https://arxiv.org/pdf/2101.10238.pdf

IEEE International Symposium on Information Theory (ISIT)•Jul 12, 2021•1 citation

List-Decoding Capacity Implies Capacity on the 𝑞-ary Symmetric Channel

Francisco Pernice, Oscar Sprumont, Mary K. Wootters

It is known that the Shannon capacity of the q-ary symmetric channel (qSC) is the same as the list-decoding capacity of an adversarial channel, raising the question of whether there is a formal (and black-box) connection between the two.We show that there is: Any linear code 𝐶 ⊆ F 𝑛 𝑞 that has superconstant minimum distance and achieves list-decoding capacity also achieves capacity on the qSC. CCS Concepts• Theory of computation → Error-correcting codes.

ACM Symposium on Theory of Computing (STOC)•Jun 15, 2025•2 citations

Exponent of the probability of list-of-L decoding error at low rates

Vladimir M. Blinovsky

There exists a lot of works devoted to obtaining the bound for the exponent of the probability of error in different channels. In this paper we prove that the expurgation exponent of the list-of-L decoding error is tight at zero rate.

IEEE International Symposium on Information Theory (ISIT)•Nov 13, 2002•2 citations

Random Coding Bound for the Reliability Function in Quantum Channel: General Case

Vladimir M. Blinovsky

We complete the proof of conjecture, which allows to complete the derivation of the random coding bound for the reliability function in quantum channel in the case of arbitrary signal states

arXiv:1112.4876•Dec 20, 2011•0 citations

List-Message Passing Achieves Capacity on the q-ary Symmetric Channel for Large q

Fan Zhang, Henry D. Pfister

We discuss and analyze a list-message-passing decoder with verification for low-density parity-check (LDPC) codes on the q-ary symmetric channel (q-SC). Rather than passing messages consisting of symbol probabilities, we pass lists of possible symbols and mark very likely symbols as verified. The density evolution (DE) equations for this decoder are derived and used to compute decoding thresholds. If the maximum list-size is unbounded, then we find that any capacity-achieving LDPC code for the binary erasure channel can be used to achieve capacity on the q-SC for large q. The decoding thresholds are also computed via DE for the case where each list is truncated to satisfy a maximum list-size constraint. The probability of false verification is considered for this case, and techniques are discussed to mitigate the problem. Optimization of the degree distribution is also used to improve the threshold for a fixed maximum list size. Finally, the proposed algorithm is compared with a variety of other algorithms using both density evolution thresholds and simulation results.

Globecom•Nov 1, 2007•21 citations
We discuss and analyze a list-message-passing decoder with verification for low-density parity-check (LDPC) codes on the q-ary symmetric channel (q-SC). Rather than passing messages consisting of symbol probabilities, we pass lists of possible symbols and mark very likely symbols as verified. The density evolution (DE) equations for this decoder are derived and used to compute decoding thresholds. If the maximum list-size is unbounded, then we find that any capacity-achieving LDPC code for the binary erasure channel can be used to achieve capacity on the q-SC for large q. The decoding thresholds are also computed via DE for the case where each list is truncated to satisfy a maximum list-size constraint. The probability of false verification is considered for this case, and techniques are discussed to mitigate the problem. Optimization of the degree distribution is also used to improve the threshold for a fixed maximum list size. Finally, the proposed algorithm is compared with a variety of other algorithms using both density evolution thresholds and simulation results.