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

Conference on Innovations in Theoretical Computer Science

Linear time decoding of regular expander codes

Michael Viderman

Published Jan 8, 2012• 8 citations
Publisher

Abstract

Sipser and Spielman (IEEE IT, [1996]) showed that any c , d )-regular expander code with expansion parameter >¾ is decodable in linear time from a constant fraction of errors. Feldman et al. (IEEE IT, [2007]) proved that expansion parameter >⅔ + 1/3c is sufficient to correct a constant fraction of errors in polynomial time using LP decoding. In this work, we give a simple combinatorial algorithm that achieves even better parameters. In particular, our algorithm runs in linear time and works for any expansion parameter >⅔ − 1/6c. We also prove that our decoding algorithm can be executed in logarithmic time on a linear number of parallel processors.

DOI
10.1145/2090236.2090251

Related papers

Fast Decoding of Expander Codes

Michael C. Dowling, Shuhong Gao

Expander codes are Tanner codes defined on sparse graphs that have good expansion properties. Sipser and Spielman (1996) showed that there is a linear-time decoding algorithm for expander codes when the vertex expansion is at least 3/4 and the number of errors corrected is a constant fraction of the code length. Later, Feldman et al. (2007) gave a decoding algorithm that allows the expansion to be 2/3 + 1/(3c), where $c$ is the left degree of the underlying bipartite graph, at the expense of polynomial-time decoding complexity. Recently, Viderman (2013) further improved the expansion parameter to $2/3 - 1/(6c)$ , and the decoding algorithm runs in linear time. These results are for expander codes whose inner codes are parity-check codes. By using stronger inner codes, Chilappagari et al. (2010) showed that there is a linear-time decoding algorithm for every vertex expansion greater than 1/2. In this paper, it is shown that for every vertex expansion, there is a linear-time decoding algorithm for expander codes (using inner codes with minimum distance depending on the vertex expansion), and that the number of errors corrected is a constant fraction of the code length.

IEEE Transactions on Information Theory•Jul 12, 2017•4 citations

Linear-time decoding from a constant fraction of errors for irregular expander codes

Rutuja Kshirsagar, Gretchen L. Matthews

In this paper, we present a linear-time decoding algorithm for expander codes based on irregular graphs of any positive vertex expansion factor [Formula: see text] and inner codes with a minimum distance of at least [Formula: see text], where [Formula: see text] is the maximum right degree. The algorithm corrects a constant fraction of errors. It builds on two thrusts. The first is a series of works starting with that of Sipser and Spielman [Expander codes, IEEE Trans. Inf. Theory 42(6) (1996) 1710–1722] demonstrating that an asymptotically good family of error-correcting codes that can be decoded in linear time even from a constant fraction of errors in a received word provided [Formula: see text] is at least [Formula: see text] and continuing to the results of Gao and Dowling [Fast decoding of expander codes, IEEE Trans. Inf. Theory 64(2) (2018) 972–978], which only require [Formula: see text] provided the inner code minimum distance is sufficiently large. The second is the improved performance of LDPC codes based on irregular graphs demonstrated by Luby et al. [Improved low- density parity-check codes using irregular graphs, IEEE Trans. Inf. Theory 47(2) (2001) 585–598] and Richardson et al. [Design of capacity- approaching irregular low-density parity-check codes, IEEE Trans. Inf. Theory 47(2) (2001) 619–637]. The algorithm presented in this paper allows for irregular or regular graph-based constructions and uses inner codes of appropriate lengths as checks rather than simple parity-checks.

Journal of Algebra and Its Applications•Apr 16, 2025•0 citations

On expander codes

Gilles Zémor

Sipser and Spielman (see ibid., vol.42, p.1717-22, Nov. 1996) have introduced a constructive family of asymptotically good linear error-correcting codes-expander codes-together with a simple parallel algorithm that will always remove a constant fraction of errors. We introduce a variation on their decoding algorithm that, with no extra cost in complexity, provably corrects up to 12 times more errors.

IEEE Transactions on Information Theory•Jan 1, 2001•137 citations

Generalized minimum distance iterative decoding of expander codes

Vitaly Skachek, Ron M. Roth

Recently, G. Zemor (see IEEE Trans. Inf. Theory, vol.47, p.835-7, 2001) proposed an improvement on the Sipser-Spielman analysis of expander codes (Sipser, M. and Spielman, D.A., IEEE Trans. Inf. Theory, vol.42 , p.1710-22, 1996) and presented a linear-time iterative decoder that can correct a number of errors up to approximately 1/4 the known lower bound on the minimum distance of the code. We propose an improvement on Zemor's decoder for F=GF(2), with the number of correctable errors becoming close to half the lower bound on the minimum distance. The improvement is obtained by inserting into the decoding algorithm features akin to generalized minimum distance decoding of concatenated codes.

IEEE Information Theory Workshop (ITW)•Mar 1, 2004•27 citations

When Can an Expander Code Correct Ω(n) Errors in O(n) Time?

Yuanting Shen, Chong Shangguan, Minghui Ouyang +1 more

Tanner codes are error-correcting codes built from a bipartite graphGand a short inner codeC0. Expander codes are a special type of Tanner code, where the graph is highly interconnected, ensuring stronger error correction capabilities. This paper is motivated by the following natural and fundamental problem in decoding expander codes: What are the sufficient and necessary conditions that δ ∈ [0, 1] andd0∈ N must satisfy, so thateverybipartite expanderGwith vertex expansion ratio δ andeverylinear inner codeC0with minimum distanced0together define an expander code that corrects Ω(n) errors inO(n) time? ForC0being the parity-check code, the landmark work of Sipser and Spielman (IEEE-TIT’96) showed that δ > 3/4 is sufficient; later, Viderman (ACM-TOCT’13) improved this to δ > 2/3 - Ω(1) and he also showed that δ > 1/2 is necessary. For general linear codeC0, the previously best-known result of Dowling and Gao (IEEE-TIT’18) showed thatd0= Ω(cδ-2) is sufficient, wherecis the left-degree ofG. We present a near-optimal solution to the above problem for generalC0by showing that δd0> 3 is sufficient and δd0> 1 is necessary, thereby significantly improving Dowling-Gao’s result. To prove the sufficient condition, we present two novel algorithms for decoding arbitrary expander codes withδd0> 3, where the first algorithm is deterministic, and the second one is randomized and has a larger decoding radius. To prove the necessary condition, we generalize the aforementioned necessary result of Viderman, and construct for every pair of δ,d0with δd0=1, an expander code with constant distance, that only corrects a constant number of errors.

IEEE Transactions on Information Theory•Jul 7, 2025•0 citations

LP decoding of expander codes: a simpler proof

Michael Viderman

A code $C \subseteq \F_2^n$ is a $(c,ε,δ)$-expander code if it has a Tanner graph, where every variable node has degree $c$, and every subset of variable nodes $L_0$ such that $|L_0|\leq δn$ has at least $εc |L_0|$ neighbors. Feldman et al. (IEEE IT, 2007) proved that LP decoding corrects $\frac{3ε-2}{2ε-1} \cdot (δn-1)$ errors of $(c,ε,δ)$-expander code, where $ε> 2/3+\frac{1}{3c}$. In this paper, we provide a simpler proof of their result and show that this result holds for every expansion parameter $ε> 2/3$.

arXiv:1206.2568•Jun 12, 2012•2 citations
Sipser and Spielman (IEEE IT, [1996]) showed that any c , d )-regular expander code with expansion parameter >¾ is decodable in linear time from a constant fraction of errors. Feldman et al. (IEEE IT, [2007]) proved that expansion parameter >⅔ + 1/3c is sufficient to correct a constant fraction of errors in polynomial time using LP decoding. In this work, we give a simple combinatorial algorithm that achieves even better parameters. In particular, our algorithm runs in linear time and works for any expansion parameter >⅔ − 1/6c. We also prove that our decoding algorithm can be executed in logarithmic time on a linear number of parallel processors.
Expander codes are Tanner codes defined on sparse graphs that have good expansion properties. Sipser and Spielman (1996) showed that there is a linear-time decoding algorithm for expander codes when the vertex expansion is at least 3/4 and the number of errors corrected is a constant fraction of the code length. Later, Feldman et al. (2007) gave a decoding algorithm that allows the expansion to be 2/3 + 1/(3c), where ccc is the left degree of the underlying bipartite graph, at the expense of polynomial-time decoding complexity. Recently, Viderman (2013) further improved the expansion parameter to 2/3−1/(6c)2/3 - 1/(6c)2/3−1/(6c) , and the decoding algorithm runs in linear time. These results are for expander codes whose inner codes are parity-check codes. By using stronger inner codes, Chilappagari et al. (2010) showed that there is a linear-time decoding algorithm for every vertex expansion greater than 1/2. In this paper, it is shown that for every vertex expansion, there is a linear-time decoding algorithm for expander codes (using inner codes with minimum distance depending on the vertex expansion), and that the number of errors corrected is a constant fraction of the code length.
In this paper, we present a linear-time decoding algorithm for expander codes based on irregular graphs of any positive vertex expansion factor [Formula: see text] and inner codes with a minimum distance of at least [Formula: see text], where [Formula: see text] is the maximum right degree. The algorithm corrects a constant fraction of errors. It builds on two thrusts. The first is a series of works starting with that of Sipser and Spielman [Expander codes, IEEE Trans. Inf. Theory 42(6) (1996) 1710–1722] demonstrating that an asymptotically good family of error-correcting codes that can be decoded in linear time even from a constant fraction of errors in a received word provided [Formula: see text] is at least [Formula: see text] and continuing to the results of Gao and Dowling [Fast decoding of expander codes, IEEE Trans. Inf. Theory 64(2) (2018) 972–978], which only require [Formula: see text] provided the inner code minimum distance is sufficiently large. The second is the improved performance of LDPC codes based on irregular graphs demonstrated by Luby et al. [Improved low- density parity-check codes using irregular graphs, IEEE Trans. Inf. Theory 47(2) (2001) 585–598] and Richardson et al. [Design of capacity- approaching irregular low-density parity-check codes, IEEE Trans. Inf. Theory 47(2) (2001) 619–637]. The algorithm presented in this paper allows for irregular or regular graph-based constructions and uses inner codes of appropriate lengths as checks rather than simple parity-checks.
Recently, G. Zemor (see IEEE Trans. Inf. Theory, vol.47, p.835-7, 2001) proposed an improvement on the Sipser-Spielman analysis of expander codes (Sipser, M. and Spielman, D.A., IEEE Trans. Inf. Theory, vol.42 , p.1710-22, 1996) and presented a linear-time iterative decoder that can correct a number of errors up to approximately 1/4 the known lower bound on the minimum distance of the code. We propose an improvement on Zemor's decoder for F=GF(2), with the number of correctable errors becoming close to half the lower bound on the minimum distance. The improvement is obtained by inserting into the decoding algorithm features akin to generalized minimum distance decoding of concatenated codes.
Tanner codes are error-correcting codes built from a bipartite graphGand a short inner codeC0. Expander codes are a special type of Tanner code, where the graph is highly interconnected, ensuring stronger error correction capabilities. This paper is motivated by the following natural and fundamental problem in decoding expander codes: What are the sufficient and necessary conditions that δ ∈ [0, 1] andd0∈ N must satisfy, so thateverybipartite expanderGwith vertex expansion ratio δ andeverylinear inner codeC0with minimum distanced0together define an expander code that corrects Ω(n) errors inO(n) time? ForC0being the parity-check code, the landmark work of Sipser and Spielman (IEEE-TIT’96) showed that δ > 3/4 is sufficient; later, Viderman (ACM-TOCT’13) improved this to δ > 2/3 - Ω(1) and he also showed that δ > 1/2 is necessary. For general linear codeC0, the previously best-known result of Dowling and Gao (IEEE-TIT’18) showed thatd0= Ω(cδ-2) is sufficient, wherecis the left-degree ofG. We present a near-optimal solution to the above problem for generalC0by showing that δd0> 3 is sufficient and δd0> 1 is necessary, thereby significantly improving Dowling-Gao’s result. To prove the sufficient condition, we present two novel algorithms for decoding arbitrary expander codes withδd0> 3, where the first algorithm is deterministic, and the second one is randomized and has a larger decoding radius. To prove the necessary condition, we generalize the aforementioned necessary result of Viderman, and construct for every pair of δ,d0with δd0=1, an expander code with constant distance, that only corrects a constant number of errors.
A code $C \subseteq \F_2^n$ is a (c,ε,δ)(c,ε,δ)(c,ε,δ)-expander code if it has a Tanner graph, where every variable node has degree ccc, and every subset of variable nodes L0L_0L0​ such that ∣L0∣≤δn|L_0|\leq δn∣L0​∣≤δn has at least εc∣L0∣εc |L_0|εc∣L0​∣ neighbors. Feldman et al. (IEEE IT, 2007) proved that LP decoding corrects 3ε−22ε−1⋅(δn−1)\frac{3ε-2}{2ε-1} \cdot (δn-1)2ε−13ε−2​⋅(δn−1) errors of (c,ε,δ)(c,ε,δ)(c,ε,δ)-expander code, where ε>2/3+13cε> 2/3+\frac{1}{3c}ε>2/3+3c1​. In this paper, we provide a simpler proof of their result and show that this result holds for every expansion parameter ε>2/3ε> 2/3ε>2/3.