On the Block Error Probability of LP Decoding of LDPC Codes

Pascal O. Vontobel; Ralf Koetter

REVIEW

On the Block Error Probability of LP Decoding of LDPC Codes

Ralf Koetter, Pascal O. Vontobel

Information Theory · Submitted 26 Feb 2006 · 12 references

Pith's verdict: First analytic LP-decoding threshold for regular LDPC codes, with a clean dual-witness construction—but the load-bearing Lemma 4 is asserted, not proved, so the theorem is conditional as written.

T0 · AI review

How this review was made: An AI referee (deepseek-v4-flash) read the paper on August 28, 2026 and answered a fixed list of questions about it. T0 is the starting level every paper gets. The levels describe how deeply Pith has checked the paper, never the authors.

T0 AI review An AI read the paper and answered a fixed list of questions.
T1 Audit Automatic checks that the references and files the paper relies on exist and match.
T2 Compute The paper's code or calculations re-run with the same results.
T3 Formal statement The claims written out in a formal math language a computer can read.
T4 Proof Those claims proved, and the proof checked by computer.

How Pith checks papers →

· 4 major objections · 4 minor · Ask about this paper · The compiled record · Read the full review →

Challenge this review Comment (0) Read on arXiv ↗

Cite ▾

arXiv IDcs/0602086 (version 1)

Pith IDFEAVZIMQ, Pith's permanent record of this paper and its review

CitationPascal O. Vontobel, Ralf Koetter. "On the Block Error Probability of LP Decoding of LDPC Codes." arXiv:cs/0602086 (2006). https://pith.science/paper/FEAVZIMQ

Cite this reviewBibTeX for Pith's review of this paper

Claim paper

Why Pith says this

Highlight any text to comment on it.

Editor's note

read the letter

Colleague,

The paper transfers Wiberg's min-sum threshold analysis to LP decoding of regular LDPC codes. That is genuinely new: Wiberg and Lentmaier et al. had thresholds for MSA, not for LP. The construction here—building dual witnesses from MSA messages on computation trees, with an attenuated averaging of tree assignments—is a real extension, and the resulting bound gamma <= 1/(K-1) with doubly exponential error decay is the first analytic LP threshold of that shape. No fitted parameters, no circularity; the self-citation at the end is just a comparison with their own lower bound.

What the paper does well: the dual LP setup in Section III is clean, and Lemmas 1–3 are straightforward and correct. The telescoping argument for the generalized assignment tau(L, alpha) is elegant and makes the choice beta = 1/(K-1) natural. The Gallager girth argument for equation (1) is standard and properly cited.

The soft spot is exactly where the reader's report puts it: Lemma 4 is the load-bearing bridge from tree-MSA success (event A_j) to a dual witness with theta_j = 0, and its proof is a paragraph of intuition, not a derivation. The decomposition mu_i = rho_i - (J-1)^L nu_i^(1) is asserted; the identification of rho_i as a 'cost summary' is never made formal; and the claim that A_j implies > 0 for all even-weight b is stated rather than shown. Because min-sum is piecewise linear, it is not obvious that the -U initialization separates cleanly into an additive leaf term at the root message. This is not a manufactured nitpick: without Lemma 4, Lemmas 1–3 give a dual-feasible point but not one with zero objective, so no LP optimality follows. The probability estimate in Eq. (2) also union-bounds only minimal-tree codewords; the text does not justify ignoring non-minimal local words, so that part inherits the same informality.

That said, the gap looks fixable. The decomposition is plausible; what is missing is a proper induction on the computation tree that tracks the actual log-likelihood cost difference. If such an induction goes through, the theorem holds. As written, it is conditional.

This paper deserves a serious referee. It is a significant result in the coding theory subfield, the main idea is right, and the flaw is a proof gap, not a conceptual one. I would send it out. I would also bring it to the reading group: the gap in Lemma 4 is exactly the kind of thing a group can work through.

Referee report

Significance

If correct, this would be a significant contribution: it would provide the first analytic threshold and error exponent for LP decoding of regular LDPC codes, closely paralleling Wiberg's earlier MSA threshold and providing a concrete comparison with the authors' lower bound in [10]. The use of dual witnesses is standard and the construction via MSA messages is conceptually attractive. The paper contains no fitted parameters, and the claimed threshold γ ≤ 1/(K−1) is explicit and testable. However, the proof as written has a load-bearing gap: Lemma 4, which is the only bridge from tree-MSA success to LP dual optimality, is asserted rather than proven, and the probability bound in Eq. (2) does not follow from the stated union-bound argument. These issues prevent the central claim from being considered established in the current manuscript.

Major objections (4)

[Section IV, Lemma 4] Lemma 4 is the only step that converts successful tree-MSA decoding (event A_j) into a dual witness with θ_j = 0, but its proof is an assertion. The decomposition µ(L)_{i,j0} = ρ_i − (J−1)^L ν(1)_{i,j0} is not derived from the MSA update equations; since min-sum is piecewise linear, the effect of the −U initialization on the root message is not obviously an exact additive leaf term with coefficient (J−1)^L. Moreover, ρ_i is not formally identified with the log-likelihood cost difference of a specific tree word, and the claim that event A_j is equivalent to ⟨ρ,b⟩ > 0 for all even-weight b is stated without proof. Because Lemma 4 is what forces θ_j = 0 for every check node, the threshold γ ≤ 1/(K−1) in Theorem 5 is unsupported as written unless this lemma is proved rigorously.
[Section IV, Eq. (2)] The bound P(A_j) < K/2 ((K−1)γ)^{2((J−1)^L−1)/(J−2)} is obtained by union-bounding only over 'minimal-tree codewords.' A union bound requires an upper bound on the sum of pairwise error probabilities over all nonzero tree codewords. Restricting the summation to minimal codewords gives a lower bound on that total sum, not an upper bound on the probability of the union. To make Eq. (2) valid, the authors must supply a weight-enumerator argument showing that contributions from all non-minimal tree codewords can be absorbed into the stated doubly exponential bound (e.g., by summing over all weights with a geometric bound).
[Section IV, Theorem 5] Theorem 5 states the condition γ ≤ 1/(K−1), but the paragraph immediately before Eq. (2) says that P(A_j) decreases doubly exponentially only if γ < 1/(K−1). If γ = 1/(K−1), the factor (K−1)γ equals 1 in Eq. (2), yielding P(A_j) < K/2, which does not tend to zero and cannot produce arbitrarily small block error probability. The theorem statement should use a strict inequality, or the proof must justify the boundary case separately.
[Section IV, paragraphs after Lemma 4] The sentence 'Lemmas 3 and 4 imply that the sum ∑_{i∈∂(j)} b_i τ*_{i,j0} has a non-negative value for any b ∈ B(K)' is a significant step that is not shown in detail. The averaged assignment τ* is a superposition of MSA messages at different levels, and it is not immediate that the non-negativity from Lemmas 3 and 4 survives the averaging and telescoping used to define τ*. Please provide an explicit expansion showing how each term in τ* is handled, especially the (J−1)^L ν(1) contribution that Lemma 4 is meant to offset.

Minor objections (4)

[Section IV, Modified MSA] The modified MSA is initially defined with ν(1) set to zero, but later the initialization is changed to ν(1) = −U. Please clarify which initialization applies to Lemmas 1–2 and which applies to Lemmas 3–4, as the two settings lead to different message values.
[Section IV, Lemmas 1 and 2] The proofs of Lemmas 1 and 2 say 'one can verify' for the key counting argument. For a journal paper, please expand these verifications or provide the explicit summation that shows the equality ∑_{j0} τ_{i,j}(j0,L) = T(L) λ_i.
[Section IV, Eq. (2)] The count of minimal-tree codewords is stated without derivation. Please include a short explanation of how the factor K/2 and the exponent 2(1+(J−1)+⋯+(J−1)^{L−1}) arise from the structure of the computation tree.
[Section IV, Event A_j] The definition of event A_j is informal ('the all-zeros word on this CT is more likely than any word that corresponds to a local nonzero word'). Please give a precise definition in terms of the log-likelihood ratios on the tree, since the proof of Lemma 4 depends on this definition.

How Pith checks papers → · Full audit of this paper →

The paper

The paper claims

This paper proves that linear-programming decoding of (J,K)-regular LDPC codes achieves arbitrarily small block error probability on any memoryless channel with Bhattacharyya parameter at most 1/(K-1), with an explicit error exponent.

The reading

Linear-programming (LP) decoding of low-density parity-check (LDPC) codes had no analytic performance threshold; this paper supplies one for regular codes. The claim is that on any memoryless channel whose Bhattacharyya parameter is at most $1/(K-1)$, a sequence of $(J,K)$-regular LDPC codes satisfying a tree-neighborhood growth condition achieves arbitrarily small block error probability under LP decoding. The argument converts a min-sum algorithm running on computation trees into a dual witness for the LP, then bounds the failure probability by the weight distribution of minimal tree codewords. If correct, LP decoding inherits the same kind of threshold guarantee the min-sum algorithm already had, with an explicit error exponent. This matters because LP decoding is a tractable relaxation of maximum-likelihood decoding, so a provable threshold tells system designers where it can be relied on.

What carries the argument

The load-bearing object is the dual linear program and the dual witness produced from the min-sum algorithm. For each check node $j_0$, the messages on a computation tree of depth $L$ are assigned to dual variables $\tau_{i,j}$, scaled by attenuation factors $\alpha_\ell = (K-1)^{-\ell}$, and summing these assignments over all check nodes yields a dual-feasible point. The decisive identity is the representation $\mu^{(L)}_{i,j_0} = \rho_i - (J-1)^L \nu^{(1)}_{i,j_0}$ of Lemma 4, which splits each message into the cost summary $\rho_i$ of the subtree and the leaf cost $(J-1)^L \nu^{(1)}_{i,j_0}$. Under the event that the all-zero word beats every local nonzero word on the tree, the inner product $\langle \rho, b\rangle$ is positive for every even-weight local word $b$, which is exactly the check-node dual constraint. Lemma 3 keeps the reconstructed dual point feasible for all nonzero local words, and a standard graph construction guarantees the needed tree-like neighborhoods for $L \le \frac{\log N}{2\log((J-1)(K-1))}-\kappa$.

Extended reading notes

Core claim

The central discovery is Theorem 5: for a sequence of $(J,K)$-regular LDPC codes whose Tanner graphs have no short cycles in the neighborhoods used by the decoder (equation (1)), LP decoding has word error probability $P_W < \eta_1 2^{-\eta_2 N^{\frac{\log(J-1)}{2\log((J-1)(K-1))}}}$ on any memoryless channel with Bhattacharyya parameter $\gamma \le 1/(K-1)$. The proof builds a dual-feasible point by summing min-sum message assignments over computation trees rooted at every check node, attenuating messages by depth. Lemmas 3 and 4 show this point certifies the all-zero codeword whenever every local tree favors the all-zero word. A union bound over check nodes, using the number of minimal tree codewords $\frac{K}{2}(K-1)^{2(1+(J-1)+\cdots+(J-1)^{L-1})}$, makes the per-check failure probability doubly exponential in $L$ when $\gamma < 1/(K-1)$.

Load-bearing premise

The proof's linchpin is the unproved local equivalence in Lemma 4: the event that the all-zero word wins on a computation tree is taken to be equivalent to the non-negativity of the corresponding check-node inner product; if that equivalence fails, the dual witness may not exist and the threshold $\gamma \le 1/(K-1)$ is unsupported.

Editorial extensions

If this is right

LP decoding of regular LDPC codes has a rigorous threshold phenomenon: below $\gamma = 1/(K-1)$ the all-zero codeword is certified as the LP optimum with high probability.
The block error probability decays doubly exponentially in the number of min-sum iterations and as a stretched exponential in block length, with exponent $\log(J-1)/(2\log((J-1)(K-1)))$.
The result applies to every memoryless binary-input output-symmetric channel, so the threshold is channel-universal up to the Bhattacharyya parameter.
On the AWGN channel the new upper bound and the graph-cover lower bound bracket the LP error exponent, leaving only a constant factor in the exponent undetermined.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The threshold $\gamma \le 1/(K-1)$ is likely not tight, because the paper's union bound over minimal tree codewords discards the shape of the message distribution; tracking that distribution on the tree could raise the threshold, though the paper does not claim this.
The computation-tree dual-witness construction suggests a general recipe: any message-passing decoder whose local cost summaries add over trees can be converted into an LP dual certificate, pointing to thresholds for irregular or generalized LDPC codes that the paper does not treat.
The proof is built around the all-zero codeword and symmetric channels; extending the threshold to asymmetric channels or to arbitrary transmitted codewords would require a genuinely different argument, since the fundamental polytope is not fully symmetric.
Because the lower bound applies to all regular codes while the upper bound needs tree-like neighborhoods, the gap between them could be investigated by simulating LP decoding on graphs with many short cycles, a question the paper leaves open.

Original abstract

In his thesis, Wiberg showed the existence of thresholds for families of regular low-density parity-check codes under min-sum algorithm decoding. He also derived analytic bounds on these thresholds. In this paper, we formulate similar results for linear programming decoding of regular low-density parity-check codes.

The compiled record

The paper's own sentences, arranged, kept beside the review and separate from it. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.

Compiled by classifier-1.13-20260917 via OpenRouter, question bank abstract-p1-20260923, 2026-09-23: 1 request, 2,827 input tokens, $0.0001 reported.

What the abstract itself states, as probabilities: claims first 0.07 · states limitation 0.06 · human participants 0.02 · controlled comparison 0.09 · randomized assignment 0.01 · states quantitative result 0.11 · compares with prior results 0.85 · mentions code or data availability 0.02.

The abstract, sentence by sentence

arXiv listing abstract v1. Results and the main claim are underlined; show every role.

In his thesis, Wiberg showed the existence of thresholds for families of regular low-density parity-check codes under min-sum algorithm decoding. He also derived analytic bounds on these thresholds. In this paper, we formulate similar results for linear programming decoding of regular low-density parity-check codes.

background contribution method result interpretation main claim

What the classifier reports for each sentence. The number is the probability it gave the label.
#	sentence	role	the authors' own work	states the main conclusion	strength
s0	In his thesis, Wiberg showed the existence of thresholds for families of regular low-density parity-check codes under min-sum algorithm decoding.	background 1.00	0.03	0.03	asserted 1.00
s1	He also derived analytic bounds on these thresholds.	background 1.00	0.04	0.03	asserted 1.00
s2	In this paper, we formulate similar results for linear programming decoding of regular low-density parity-check codes.	contribution 1.00	0.91	0.35	asserted 0.97

What kind of paper the classifier reports this is: theoretical result 1.00 · evidence from proof or derivation 0.97.

What was examined, and what was not

sources read

arXiv listing abstract v1

not examined

full text
figures and tables
references and citing sentences
relations to other papers

levels run

P abstract

not run

S sections
T body sentences
C citations
R cross-paper relations

Every quoted sentence on this record is the authors'. Every label is from Pith's closed vocabulary, with the probability shown beside it. Every number in the measurements table is the authors', checked by code. Record as JSON

References

Works cited (12)

[10]

P. O. V ontobel and R. Koetter, “Graph-cover decoding an d finite-length analysis of message-passing iterative decoding of LDPC cod es,” submit- ted to IEEE Trans. Inform. Theory, available online under http:// www.arxiv.org/abs/cs.IT/0512078, Dec. 2005

View on Pith arXiv 2005
[1]

N. Wiberg, Codes and Decoding on General Graphs . PhD thesis, Link¨ oping University, Sweden, 1996

View on Pith 1996
[2]

M. G. Luby, M. Mitzenmacher, M. A. Shokrollahi, D. A. Spie lman, and V . Stemann, “Practical loss-resilient codes,” in Proc. 29th Annual ACM Symp. on Theory of Computing , pp. 150–159, 1997

View on Pith 1997
[3]

M. G. Luby, M. Mitzenmacher, and M. A. Shokrollahi, “Anal ysis of random processes via and-or tree evaluation,” in Proc. 9th Annual ACM- SIAM Symp. on Discrete Algorithms , pp. 364–373, 1998

View on Pith 1998
[4]

T. J. Richardson and R. L. Urbanke, “The capacity of low-d ensity parity- check codes under message-passing decoding,” IEEE Trans. on Inform. Theory, vol. IT–47, no. 2, pp. 599–618, 2001

View on Pith 2001
[5]

M. Lentmaier, D. V . Truhachev, D. J. Costello, Jr., and K. Zigangirov, “On the block error probability of iteratively decoded LDPC codes,” in 5th ITG Conference on Source and Channel Coding , (Erlangen, Germany), Jan. 14-16 2004

View on Pith 2004
[6]

H. Jin and T. Richardson, “Block error iterative decodin g capacity for LDPC codes,” inProc. IEEE Intern. Symp. on Inform. Theory, (Adelaide, Australia), pp. 52 – 56, Sep. 4–9 2005

View on Pith 2005
[7]

J. Feldman, Decoding Error-Correcting Codes via Linear Program- ming. PhD thesis, Massachusetts Institute of Technology, Cambr idge, MA, 2003. Available online under http://www.columbia.edu/ ˜jf2189/pubs.html

View on Pith 2003
[8]

J. Feldman, M. J. Wainwright, and D. R. Karger, “Using lin ear program- ming to decode binary linear codes,” IEEE Trans. on Inform. Theory , vol. IT–51, no. 3, pp. 954–972, 2005

View on Pith 2005
[9]

R. Koetter and P. O. V ontobel, “Graph covers and iterativ e decoding of finite-length codes,” in Proc. 3rd Intern. Symp. on Turbo Codes and Related Topics, (Brest, France), pp. 75–82, Sept. 1–5 2003

View on Pith 2003
[11]

J. Feldman, T. Malkin, C. Stein, R. A. Servedio, and M. J. Wainwright, “LP decoding corrects a constant fraction of errors,” in Proc. IEEE Intern. Symp. on Inform. Theory , (Chicago, IL, USA), p. 68, June 27– July 2 2004

View on Pith 2004
[12]

R. G. Gallager, Low-Density Parity-Check Codes . M.I.T. Press, Cam- bridge, MA, 1963. Available online under http://web.mit.edu/ gallager/www/pages/ldpc.pdf

View on Pith 1963

How the literature uses it

1 arXiv paper cite this in 1 sentence

Each citing sentence is taken from the citing paper's LaTeX source and typed by Pith's classifier. A label appears at probability 0.8 or more (0.95 for support), a contest at 0.7 or more; the quoted words are the citing authors'. How each label was checked · JSON

Papers citing it

Cites it as background 1 paper

Lower bounds on the LP decoding thresholds of LDPC codes where obtained in [ref] under the assumption that the graph has a logarithmic girth, and upper bounds were obtained in [ref] .

Impact of redundant checks on the LP decoding thresholds of LDPC codes · Introduction · 0.93

Discussion

Disagree with the review, or know something it missed? Leave a comment, highlight any passage above to comment on it, or challenge this review formally.

[1] [10]

P. O. V ontobel and R. Koetter, “Graph-cover decoding an d finite-length analysis of message-passing iterative decoding of LDPC cod es,” submit- ted to IEEE Trans. Inform. Theory, available online under http:// www.arxiv.org/abs/cs.IT/0512078, Dec. 2005

View on Pith arXiv 2005

[2] [1]

N. Wiberg, Codes and Decoding on General Graphs . PhD thesis, Link¨ oping University, Sweden, 1996

View on Pith 1996

[3] [2]

M. G. Luby, M. Mitzenmacher, M. A. Shokrollahi, D. A. Spie lman, and V . Stemann, “Practical loss-resilient codes,” in Proc. 29th Annual ACM Symp. on Theory of Computing , pp. 150–159, 1997

View on Pith 1997

[4] [3]

M. G. Luby, M. Mitzenmacher, and M. A. Shokrollahi, “Anal ysis of random processes via and-or tree evaluation,” in Proc. 9th Annual ACM- SIAM Symp. on Discrete Algorithms , pp. 364–373, 1998

View on Pith 1998

[5] [4]

T. J. Richardson and R. L. Urbanke, “The capacity of low-d ensity parity- check codes under message-passing decoding,” IEEE Trans. on Inform. Theory, vol. IT–47, no. 2, pp. 599–618, 2001

View on Pith 2001

[6] [5]

M. Lentmaier, D. V . Truhachev, D. J. Costello, Jr., and K. Zigangirov, “On the block error probability of iteratively decoded LDPC codes,” in 5th ITG Conference on Source and Channel Coding , (Erlangen, Germany), Jan. 14-16 2004

View on Pith 2004

[7] [6]

H. Jin and T. Richardson, “Block error iterative decodin g capacity for LDPC codes,” inProc. IEEE Intern. Symp. on Inform. Theory, (Adelaide, Australia), pp. 52 – 56, Sep. 4–9 2005

View on Pith 2005

[8] [7]

J. Feldman, Decoding Error-Correcting Codes via Linear Program- ming. PhD thesis, Massachusetts Institute of Technology, Cambr idge, MA, 2003. Available online under http://www.columbia.edu/ ˜jf2189/pubs.html

View on Pith 2003

[9] [8]

J. Feldman, M. J. Wainwright, and D. R. Karger, “Using lin ear program- ming to decode binary linear codes,” IEEE Trans. on Inform. Theory , vol. IT–51, no. 3, pp. 954–972, 2005

View on Pith 2005

[10] [9]

R. Koetter and P. O. V ontobel, “Graph covers and iterativ e decoding of finite-length codes,” in Proc. 3rd Intern. Symp. on Turbo Codes and Related Topics, (Brest, France), pp. 75–82, Sept. 1–5 2003

View on Pith 2003

[11] [11]

J. Feldman, T. Malkin, C. Stein, R. A. Servedio, and M. J. Wainwright, “LP decoding corrects a constant fraction of errors,” in Proc. IEEE Intern. Symp. on Inform. Theory , (Chicago, IL, USA), p. 68, June 27– July 2 2004

View on Pith 2004

[12] [12]

R. G. Gallager, Low-Density Parity-Check Codes . M.I.T. Press, Cam- bridge, MA, 1963. Available online under http://web.mit.edu/ gallager/www/pages/ldpc.pdf

View on Pith 1963