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:1401.2716 · IEEE Transactions on Information Theory

Erasure List-Decodable Codes From Random and Algebraic Geometry Codes

Yang Ding, Lingfei Jin, Chaoping Xing

Published Mar 31, 2014• 5 citations
arXivHTMLPDF

Abstract

Erasure list decoding was introduced to correct a larger number of erasures by outputting a list of possible candidates. In this paper, we consider both random linear codes and algebraic geometry codes for list decoding from erasures. The contributions of this paper are twofold. First, for arbitrary 00 (R and ϵ are independent), we show that with high probability a q-ary random linear code of rate R is an erasure list-decodable code with constant list size qO(1/ϵ)that can correct a fraction 1 - R - ϵ of erasures, i.e., a random linear code achieves the information-theoretic optimal tradeoff between information rate and fraction of erasures. Second, we show that algebraic geometry codes are good erasure list-decodable codes. Precisely speaking, a q-ary algebraic geometry code of rate R from the Garcia-Stichtenoth tower can correct 1 - R - (1/√q - 1) + (1/q) - ϵ fraction of erasures with list size O(1/ϵ). This improves the Johnson bound for erasures applied to algebraic geometry codes. Furthermore, list decoding of these algebraic geometry codes can be implemented in polynomial time. Note that the code alphabet size q in this paper is constant and independent of ϵ.

DOI
10.1109/tit.2014.2314468

Related papers

Polynomial-Time Constructions of Asymptotically Good Random Access Codes from Linear Codes

Ruho Kondo, Yota Maeda

Random access codes (RACs) encode a $q$-ary input string into fewer $q$-ary symbols while allowing any requested input symbol to be recovered with probability above the random-guessing value $1/q$. However, it remains unclear what asymptotic guarantees on compression and recovery probability should be required of RACs. We address this question by introducing the notion of asymptotically good RACs and give two polynomial-time constructions. First, an $[n,k,d]_q$ linear code with $d\ge2$, together with an encoder based on its orthogonal-array property, yields an $(n,n-k)_q$-RAC with worst-case decoding success probability \[ p_{\rm wc}=\frac{1}{q}+\left(1-\frac{1}{q}\right)\frac{d-2}{n}. \] These OA-RACs are asymptotically good whenever the underlying linear codes are, and Garcia--Stichtenoth algebraic-geometry codes give a concrete polynomial-time realization. Second, a direct-sum strategy using OA-RACs derived from $q$-ary Hamming codes and the trivial $(1,1)_q$-RAC yields asymptotically good RAC families at every prescribed RAC rate $R_{\rm RAC}=(n-k)/n\in(0,1)$. Numerical results demonstrate favorable finite-length performance of both constructions.

arXiv:2610.38429•Oct 28, 2026•0 citations

On the List-Decodability of Random Self-Orthogonal Codes

Lingfei Jin, Chaoping Xing, Xiande Zhang

Guruswami et al. showed that the list-decodability of random linear codes is as good as that of general random codes. In this paper, we further strengthen the result by showing that the list-decodability of random Euclidean self-orthogonal codes is as good as that of general random codes as well, i.e., achieves the classical Gilbert-Varshamov bound. In particular, we show that, for any fixed finite field Fq, error fraction δ ∈ (0,1 - 1/q) satisfying 1 - Hq(δ) ≤ 1/2, and small ε > 0, with high probability a random Euclidean self-orthogonal code over Fqof rate 1 - Hq(δ) - ε is (δ, O(1/ε))-list-decodable. This generalizes the result of linear codes to Euclidean self-orthogonal codes. In addition, we extend the result to list decoding symplectic dual-containing codes by showing that the list-decodability of random symplectic dual-containing codes achieves the quantum Gilbert-Varshamov bound as well. This implies that list-decodability of quantum stabilizer codes can achieve the quantum Gilbert-Varshamov bound. The counting argument on self-orthogonal codes is an important ingredient to prove our result.

arXiv:1611.06673•IEEE Transactions on Information Theory•Oct 3, 2014•5 citations

Linear-Time Erasure List-Decoding of Expander Codes

Noga Ron‐Zewi, Mary K. Wootters, Gilles Zémor

We give a linear-time erasure list-decoding algorithm for expander codes. More precisely, let r > 0 be any integer. Given an inner codeC0of length d, and a d-regular bipartite expander graph G with n vertices on each side, we give an algorithm to list-decode the codeC=C(G,C0) of length nd from approximately δδrnd erasures in time n·poly (d2r/δ), where δ and δrare the relative distance and the r'th generalized relative distance ofC0, respectively. To the best of our knowledge, this is the first linear-time algorithm that can list-decode expander codes from erasures beyond their (designed) distance of approximately δ2nd. To obtain our results, we show that an approach similar to that of (Hemenway and Wootters, Information and Computation, 2018) can be used to obtain such an erasure-list-decoding algorithm with an exponentially worse dependence of the running time on r and δ; then we show how to improve the dependence of the running time on these parameters.

arXiv:2002.08579•IEEE Transactions on Information Theory•Jun 1, 2020•10 citations

Concatenated Codes with One Inner Code: Low-Rate Gilbert-Varshamov Asymptotics from Algebraic-Geometric Codes

Yota Maeda, Ruho Kondo

Constructing codes that attain the Gilbert-Varshamov (GV) bound while admitting efficient encoding and decoding is a fundamental problem in coding theory. We study concatenated codes that reuse a single binary inner code across all outer coordinates. To exploit existing encoding and decoding algorithms, we restrict the outer codes to random subcodes of scaled copies of prescribed algebraic codes and investigate their minimum distance. Our first contribution is a general upper bound on the minimum-distance failure probability that separates two terms controlled by the inner code's bias moments and the dual weight distribution of the prescribed code, together with sufficient conditions for exponential decay. Our second contribution is a concrete construction satisfying these conditions using algebraic-geometric codes from the Garcia-Stichtenoth tower. For every sufficiently small $\varepsilon>0$, we construct a family of random binary codes $C_m$ whose rates approach $\varepsilon^2$ and satisfy \[ \Pr\left[δ(C_m)\geq\frac12-\sqrt{\frac{\ln 2}{2}}\left(\varepsilon+\frac{\varepsilon^3}{2}\right)\right]\geq 1-2^{-c\varepsilon^4N_m}, \] for all sufficiently large $m$, where $N_m$ is the block length and $c>0$ is independent of $\varepsilon$ and $m$. Thus, the distance guarantee matches the leading coefficient of the GV bound at low rates. For each fixed $\varepsilon$, the construction uses a single inner encoding map throughout the family and admits polynomial-time encoding and unique decoding within a guaranteed radius. This answers the question of Doron, Mosheiff, and Wootters for subcodes of scaled algebraic geometry codes at low rates.

arXiv:2611.16179•Nov 12, 2026•0 citations

Every list-decodable code for high noise has abundant near-optimal rate puncturings

Atri Rudra, Mary K. Wootters

We show that any q-ary code with sufficiently good distance can be randomly punctured to obtain, with high probability, a code that is list decodable up to radius 1 --- 1/q --- ε with near-optimal rate and list sizes.

ACM Symposium on Theory of Computing (STOC)•May 31, 2014•65 citations

Improved Error Bounds for the Erasure/List Scheme: The Binary and Spherical Cases

Alexander Barg

We derive improved bounds on the error and erasure rate for spherical codes and for binary linear codes under Forney's erasure/list decoding scheme and prove some related results.

arXiv:cs/0407010•IEEE Transactions on Information Theory•Sep 28, 2004•8 citations
Erasure list decoding was introduced to correct a larger number of erasures by outputting a list of possible candidates. In this paper, we consider both random linear codes and algebraic geometry codes for list decoding from erasures. The contributions of this paper are twofold. First, for arbitrary 00 (R and ϵ are independent), we show that with high probability a q-ary random linear code of rate R is an erasure list-decodable code with constant list size qO(1/ϵ)that can correct a fraction 1 - R - ϵ of erasures, i.e., a random linear code achieves the information-theoretic optimal tradeoff between information rate and fraction of erasures. Second, we show that algebraic geometry codes are good erasure list-decodable codes. Precisely speaking, a q-ary algebraic geometry code of rate R from the Garcia-Stichtenoth tower can correct 1 - R - (1/√q - 1) + (1/q) - ϵ fraction of erasures with list size O(1/ϵ). This improves the Johnson bound for erasures applied to algebraic geometry codes. Furthermore, list decoding of these algebraic geometry codes can be implemented in polynomial time. Note that the code alphabet size q in this paper is constant and independent of ϵ.
Random access codes (RACs) encode a qqq-ary input string into fewer qqq-ary symbols while allowing any requested input symbol to be recovered with probability above the random-guessing value 1/q1/q1/q. However, it remains unclear what asymptotic guarantees on compression and recovery probability should be required of RACs. We address this question by introducing the notion of asymptotically good RACs and give two polynomial-time constructions. First, an [n,k,d]q[n,k,d]_q[n,k,d]q​ linear code with d≥2d\ge2d≥2, together with an encoder based on its orthogonal-array property, yields an (n,n−k)q(n,n-k)_q(n,n−k)q​-RAC with worst-case decoding success probability pwc=1q+(1−1q)d−2n. p_{\rm wc}=\frac{1}{q}+\left(1-\frac{1}{q}\right)\frac{d-2}{n}. pwc​=q1​+(1−q1​)nd−2​. These OA-RACs are asymptotically good whenever the underlying linear codes are, and Garcia--Stichtenoth algebraic-geometry codes give a concrete polynomial-time realization. Second, a direct-sum strategy using OA-RACs derived from qqq-ary Hamming codes and the trivial (1,1)q(1,1)_q(1,1)q​-RAC yields asymptotically good RAC families at every prescribed RAC rate RRAC=(n−k)/n∈(0,1)R_{\rm RAC}=(n-k)/n\in(0,1)RRAC​=(n−k)/n∈(0,1). Numerical results demonstrate favorable finite-length performance of both constructions.
Guruswami et al. showed that the list-decodability of random linear codes is as good as that of general random codes. In this paper, we further strengthen the result by showing that the list-decodability of random Euclidean self-orthogonal codes is as good as that of general random codes as well, i.e., achieves the classical Gilbert-Varshamov bound. In particular, we show that, for any fixed finite field Fq, error fraction δ ∈ (0,1 - 1/q) satisfying 1 - Hq(δ) ≤ 1/2, and small ε > 0, with high probability a random Euclidean self-orthogonal code over Fqof rate 1 - Hq(δ) - ε is (δ, O(1/ε))-list-decodable. This generalizes the result of linear codes to Euclidean self-orthogonal codes. In addition, we extend the result to list decoding symplectic dual-containing codes by showing that the list-decodability of random symplectic dual-containing codes achieves the quantum Gilbert-Varshamov bound as well. This implies that list-decodability of quantum stabilizer codes can achieve the quantum Gilbert-Varshamov bound. The counting argument on self-orthogonal codes is an important ingredient to prove our result.
We give a linear-time erasure list-decoding algorithm for expander codes. More precisely, let r > 0 be any integer. Given an inner codeC0of length d, and a d-regular bipartite expander graph G with n vertices on each side, we give an algorithm to list-decode the codeC=C(G,C0) of length nd from approximately δδrnd erasures in time n·poly (d2r/δ), where δ and δrare the relative distance and the r'th generalized relative distance ofC0, respectively. To the best of our knowledge, this is the first linear-time algorithm that can list-decode expander codes from erasures beyond their (designed) distance of approximately δ2nd. To obtain our results, we show that an approach similar to that of (Hemenway and Wootters, Information and Computation, 2018) can be used to obtain such an erasure-list-decoding algorithm with an exponentially worse dependence of the running time on r and δ; then we show how to improve the dependence of the running time on these parameters.
Constructing codes that attain the Gilbert-Varshamov (GV) bound while admitting efficient encoding and decoding is a fundamental problem in coding theory. We study concatenated codes that reuse a single binary inner code across all outer coordinates. To exploit existing encoding and decoding algorithms, we restrict the outer codes to random subcodes of scaled copies of prescribed algebraic codes and investigate their minimum distance. Our first contribution is a general upper bound on the minimum-distance failure probability that separates two terms controlled by the inner code's bias moments and the dual weight distribution of the prescribed code, together with sufficient conditions for exponential decay. Our second contribution is a concrete construction satisfying these conditions using algebraic-geometric codes from the Garcia-Stichtenoth tower. For every sufficiently small ε>0\varepsilon>0ε>0, we construct a family of random binary codes CmC_mCm​ whose rates approach ε2\varepsilon^2ε2 and satisfy Pr⁡[δ(Cm)≥12−ln⁡22(ε+ε32)]≥1−2−cε4Nm, \Pr\left[δ(C_m)\geq\frac12-\sqrt{\frac{\ln 2}{2}}\left(\varepsilon+\frac{\varepsilon^3}{2}\right)\right]\geq 1-2^{-c\varepsilon^4N_m}, Pr[δ(Cm​)≥21​−2ln2​​(ε+2ε3​)]≥1−2−cε4Nm​, for all sufficiently large mmm, where NmN_mNm​ is the block length and c>0c>0c>0 is independent of ε\varepsilonε and mmm. Thus, the distance guarantee matches the leading coefficient of the GV bound at low rates. For each fixed ε\varepsilonε, the construction uses a single inner encoding map throughout the family and admits polynomial-time encoding and unique decoding within a guaranteed radius. This answers the question of Doron, Mosheiff, and Wootters for subcodes of scaled algebraic geometry codes at low rates.