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

LP decoding of expander codes: a simpler proof

Michael Viderman

Published Jun 12, 2012• 2 citations
arXivHTMLPDF

Abstract

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

DOI
10.48550/arxiv.1206.2568

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 of regular expander codes

Michael Viderman

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.

Conference on Innovations in Theoretical Computer Science•Jan 8, 2012•8 citations

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

Kuan Cheng, Minghui Ouyang, Chong Shangguan +1 more

Tanner codes are graph-based linear codes whose parity-check matrices can be characterized by a bipartite graph $G$ together with a linear inner code $C_0$. Expander codes are Tanner codes whose defining bipartite graph $G$ has good expansion property. This paper is motivated by the following natural and fundamental problem in decoding expander codes: What are the sufficient and necessary conditions that $δ$ and $d_0$ must satisfy, so that \textit{every} bipartite expander $G$ with vertex expansion ratio $δ$ and \textit{every} linear inner code $C_0$ with minimum distance $d_0$ together define an expander code that corrects $Ω(n)$ errors in $O(n)$ time? For $C_0$ being 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 code $C_0$, the previously best-known result of Dowling and Gao (IEEE-TIT'18) showed that $d_0=Ω(cδ^{-2})$ is sufficient, where $c$ is the left-degree of $G$. In this paper, we give a near-optimal solution to the above question for general $C_0$ by showing that $δd_0>3$ is sufficient and $δd_0>1$ is necessary, thereby also significantly improving Dowling-Gao's result. We present two novel algorithms for decoding expander codes, where the first algorithm is deterministic, and the second one is randomized and has a larger decoding radius.

arXiv:2312.16087•Leibniz international proceedings in informatics•Dec 26, 2023•0 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

Improved Decoding of Tanner Codes

Zhaienhe Zhou, Zeyu Guo

In this paper, we present improved decoding algorithms for expander-based Tanner codes. We begin by developing a randomized linear-time decoding algorithm that, under the condition that$\delta d_{0}>2$, corrects up to$\alpha n$errors for a Tanner code$T\left(G, C_{0}\right)$, where$G$is a ($c, d, \alpha, \delta$) bipartite expander with$n$left vertices, and$C_{0} \subseteq \mathbb{F}_{2}^{d}$is a linear inner code with minimum distance$d_{0}$. This result improves upon the previous work of Cheng, Ouyang, Shangguan, and Shen (RANDOM 2024), which required$\delta d_{0}>3$. We further derandomize the algorithm to obtain a deterministic linear-time decoding algorithm with the same decoding radius. Our algorithm improves upon the previous deterministic algorithm of Cheng et al. by achieving a decoding radius of$\alpha n$, compared with the previous radius of$\frac{2 \alpha}{d_{0}(1+0.5 c \delta)} n$. Additionally, we investigate the size-expansion trade-off introduced by the recent work of Chen, Cheng, Li, and Ouyang (IEEE TIT 2023), and use it to provide new bounds on the minimum distance of Tanner codes. Specifically, we prove that the minimum distance of a Tanner code$T\left(G, C_{0}\right)$is approximately$f_{\delta}^{-1}\left(\frac{1}{d_{0}}\right) \alpha n$, where$f_{\delta}(\cdot)$is the Size-Expansion Function. As another application, we improve the decoding radius of our decoding algorithms from$\alpha n$to approximately$f_{\delta}^{-1}\left(\frac{2}{d_{0}}\right) \alpha n$.

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

LP Decoding Corrects a Constant Fraction of Errors

J. Feldman, Tal Malkin, Rocco A. Servedio +2 more

We show that for low-density parity-check (LDPC) codes whose Tanner graphs have sufficient expansion, the linear programming (LP) decoder of Feldman, Karger, and Wainwright can correct a constant fraction of errors. A random graph will have sufficient expansion with high probability, and recent work shows that such graphs can be constructed efficiently. A key element of our method is the use of a dual witness: a zero-valued dual solution to the decoding linear program whose existence proves decoding success. We show that as long as no more than a certain constant fraction of the bits are flipped by the channel, we can find a dual witness. This new method can be used for proving bounds on the performance of any LP decoder, even in a probabilistic setting. Our result implies that the word error rate of the LP decoder decreases exponentially in the code length under the binary-symmetric channel (BSC). This is the first such error bound for LDPC codes using an analysis based on "pseudocodewords." Recent work by Koetter and Vontobel shows that LP decoding and min-sum decoding of LDPC codes are closely related by the "graph cover" structure of their pseudocodewords; in their terminology, our result implies that that there exist families of LDPC codes where the minimum BSC pseudoweight grows linearly in the block length

IEEE Transactions on Information Theory•Jan 1, 2007•116 citations
A code C⊆\F2nC \subseteq \F_2^nC⊆\F2n​ 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.
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.
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.
Tanner codes are graph-based linear codes whose parity-check matrices can be characterized by a bipartite graph GGG together with a linear inner code C0C_0C0​. Expander codes are Tanner codes whose defining bipartite graph GGG has good expansion property. This paper is motivated by the following natural and fundamental problem in decoding expander codes: What are the sufficient and necessary conditions that δδδ and d0d_0d0​ must satisfy, so that \textit{every} bipartite expander GGG with vertex expansion ratio δδδ and \textit{every} linear inner code C0C_0C0​ with minimum distance d0d_0d0​ together define an expander code that corrects Ω(n)Ω(n)Ω(n) errors in O(n)O(n)O(n) time? For C0C_0C0​ being the parity-check code, the landmark work of Sipser and Spielman (IEEE-TIT'96) showed that δ>3/4δ>3/4δ>3/4 is sufficient; later Viderman (ACM-TOCT'13) improved this to δ>2/3−Ω(1)δ>2/3-Ω(1)δ>2/3−Ω(1) and he also showed that δ>1/2δ>1/2δ>1/2 is necessary. For general linear code C0C_0C0​, the previously best-known result of Dowling and Gao (IEEE-TIT'18) showed that d0=Ω(cδ−2)d_0=Ω(cδ^{-2})d0​=Ω(cδ−2) is sufficient, where ccc is the left-degree of GGG. In this paper, we give a near-optimal solution to the above question for general C0C_0C0​ by showing that δd0>3δd_0>3δd0​>3 is sufficient and δd0>1δd_0>1δd0​>1 is necessary, thereby also significantly improving Dowling-Gao's result. We present two novel algorithms for decoding expander codes, where the first algorithm is deterministic, and the second one is randomized and has a larger decoding radius.
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.
In this paper, we present improved decoding algorithms for expander-based Tanner codes. We begin by developing a randomized linear-time decoding algorithm that, under the condition thatδd0>2\delta d_{0}>2δd0​>2, corrects up toαn\alpha nαnerrors for a Tanner codeT(G,C0)T\left(G, C_{0}\right)T(G,C0​), whereGGGis a (c,d,α,δc, d, \alpha, \deltac,d,α,δ) bipartite expander withnnnleft vertices, andC0⊆F2dC_{0} \subseteq \mathbb{F}_{2}^{d}C0​⊆F2d​is a linear inner code with minimum distanced0d_{0}d0​. This result improves upon the previous work of Cheng, Ouyang, Shangguan, and Shen (RANDOM 2024), which requiredδd0>3\delta d_{0}>3δd0​>3. We further derandomize the algorithm to obtain a deterministic linear-time decoding algorithm with the same decoding radius. Our algorithm improves upon the previous deterministic algorithm of Cheng et al. by achieving a decoding radius ofαn\alpha nαn, compared with the previous radius of2αd0(1+0.5cδ)n\frac{2 \alpha}{d_{0}(1+0.5 c \delta)} nd0​(1+0.5cδ)2α​n. Additionally, we investigate the size-expansion trade-off introduced by the recent work of Chen, Cheng, Li, and Ouyang (IEEE TIT 2023), and use it to provide new bounds on the minimum distance of Tanner codes. Specifically, we prove that the minimum distance of a Tanner codeT(G,C0)T\left(G, C_{0}\right)T(G,C0​)is approximatelyfδ−1(1d0)αnf_{\delta}^{-1}\left(\frac{1}{d_{0}}\right) \alpha nfδ−1​(d0​1​)αn, wherefδ(⋅)f_{\delta}(\cdot)fδ​(⋅)is the Size-Expansion Function. As another application, we improve the decoding radius of our decoding algorithms fromαn\alpha nαnto approximatelyfδ−1(2d0)αnf_{\delta}^{-1}\left(\frac{2}{d_{0}}\right) \alpha nfδ−1​(d0​2​)αn.
We show that for low-density parity-check (LDPC) codes whose Tanner graphs have sufficient expansion, the linear programming (LP) decoder of Feldman, Karger, and Wainwright can correct a constant fraction of errors. A random graph will have sufficient expansion with high probability, and recent work shows that such graphs can be constructed efficiently. A key element of our method is the use of a dual witness: a zero-valued dual solution to the decoding linear program whose existence proves decoding success. We show that as long as no more than a certain constant fraction of the bits are flipped by the channel, we can find a dual witness. This new method can be used for proving bounds on the performance of any LP decoder, even in a probabilistic setting. Our result implies that the word error rate of the LP decoder decreases exponentially in the code length under the binary-symmetric channel (BSC). This is the first such error bound for LDPC codes using an analysis based on "pseudocodewords." Recent work by Koetter and Vontobel shows that LP decoding and min-sum decoding of LDPC codes are closely related by the "graph cover" structure of their pseudocodewords; in their terminology, our result implies that that there exist families of LDPC codes where the minimum BSC pseudoweight grows linearly in the block length