{"id":"93b173a7-2104-4d97-95e6-4ffa835fb3d9","arxiv_id":"cs/0602088","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":1,"one_line_summary":"A softened dual LP for LDPC decoding yields message-passing-like coordinate-ascent updates that provably converge for finite temperature, connecting LP decoding to min-sum and sum-product algorithms.","lead":"This paper introduces a coordinate-ascent algorithm for solving the dual of the linear-programming (LP) decoding problem for LDPC codes, with update rules that resemble min-sum and sum-product message passing. It argues that LP decoding can run at complexity comparable to standard iterative decoders, potentially enabling guaranteed low error rates.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Exact LP decoding claim is unproven: Lemma 4 covers only the finite-kappa softened dual; convergence to the LP optimum as kappa->infinity is left as Conjecture 6, which Sec. E shows is not a routine extension.","rationale":"The reader's verdict was CONDITIONAL, and the primary reason is the gap between the proven finite-kappa convergence of SDLPD2 and the claimed LP decoding result. My reading agrees with that assessment: the strongest claim in the abstract is that LP solvers with complexity similar to min-sum and sum-product are feasible, and that claim depends on solving the exact dual LP, not merely the softened dual. Lemma 4 proves convergence for finite kappa, but the exact LP limit is left as Conjecture 6, with Sec. E showing that coordinate ascent can fail for concave piecewise-linear objectives in general. The strict-concavity assertion in the proof of Lemma 4 is also underexplained, but it appears to be repairable by exploiting strict concavity of the check-node soft-min terms when check degrees are at least 3; thus it is not the most load-bearing gap. A computational falsification test on a small code is a concrete way to check whether Conjecture 6 actually holds, since a single non-converging run would settle the concern. The reader's conditional verdict already reflects this uncertainty, so no change to the verdict is needed.","tokens_in":13616,"tokens_out":10977,"duration_ms":99174,"concrete_test":"Run the kappa->infinity update rule of Lemma 5 (random selection in the interval) on a small code with all parity-check rows of weight at least 3, e.g., the [7,4] Hamming code or a small (3,6)-regular code. For each of many random initializations (say 10^4), iterate until the dual objective stabilizes and compare with the true DLPD2 optimum obtained from a simplex or interior-point LP solver. If any run terminates with dual objective strictly below the LP optimum, Conjecture 6 is refuted and the LP-feasibility claim fails; if all runs reach the optimum, this supports the conjecture but does not prove it.","verdict_should_be":"UNCHANGED","load_bearing_attack":"To support the abstract's claim that 'LP solvers with complexity similar to the min-sum algorithm and the sum-product algorithm are feasible,' the coordinate-ascent algorithm must converge to the optimum of the exact dual DLPD2 (the LP). The paper proves in Lemma 4 (Sec. C) that cyclic coordinate ascent converges to the maximum of the softened dual SDLPD2 for finite positive kappa. But that is a different optimization problem. The kappa->infinity limit is handled only by Lemma 5, which characterizes the coordinate-wise maximizer interval, and by Conjecture 6, which asserts that random choices in that interval converge to the LP optimum. Conjecture 6 is explicitly unproved, and Sec. E provides a concave piecewise-linear function where coordinate ascent stalls at a suboptimal point, illustrating that the standard concave-convergence argument does not carry over. Consequently, the central claim that the LP itself can be solved with min-sum/sum-product-like complexity is not established; what is established is convergence to a family of softened problems whose limit is the LP. The terse strict-concavity argument in Sec. C is a secondary issue, but the exact-LP gap is the load-bearing one.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the dual of the Feldman et al. LP decoder for LDPC codes. It introduces a primal formulation PLPD2, derives the dual DLPD2, and then softens the min operators to soft-minimum operators, giving SDLPD2 with inverse temperature κ. The main algorithmic contributions are a closed-form coordinate-ascent update for a single dual edge (Lemma 3), a convergence claim for cyclic coordinate ascent for finite κ (Lemma 4), and a characterization of the coordinate-wise maximizer interval in the hard-min limit κ→∞ (Lemma 5). The authors conjecture that a randomized version of the hard-min update converges to the LP optimum (Conjecture 6) and discuss in Sec. E why the standard concave-convergence argument fails. They also propose an incremental subgradient method and report word-error-rate simulations for a [1000,500] (3,6)-regular code using the Lemma 5 update.","tokens_in":14015,"tokens_out":6923,"duration_ms":67414,"significance":"If the finite-κ convergence result and the update rules are correct, this is a valuable and clean connection between LP decoding and message-passing algorithms: the per-edge updates are explicit and computable by sum-product-style message passing, and the derivation is parameter-free rather than fitted to simulation data. The dual formulation and the interval characterization in Lemma 5 are useful tools. However, the headline feasibility claim for LP decoding with min-sum/sum-product-like complexity is established only for the softened objective; the exact-LP limit rests on an explicitly stated conjecture. The paper is honest about this gap, and the underlying derivations are still of interest, but the abstract and conclusions need to be qualified accordingly.","major_comments":[{"comment":"The abstract and conclusions claim that LP solvers with complexity similar to min-sum and sum-product algorithms are feasible. What is actually proven is that cyclic coordinate ascent converges to the maximum of the softened dual SDLPD2 for each finite κ (Lemma 4). The κ→∞ limit to the exact dual DLPD2, and hence to the LP decoder, is left as Conjecture 6, and the manuscript itself states that no proof is available. Sec. E reinforces this by giving a concave piecewise-linear example where the coordinate-ascent argument fails, so the limit is not a routine extension. The order of limits is also delicate: even if the algorithm converges for every finite κ, the number of iterations may grow without bound as κ increases, and the hard-min trajectory is not controlled. Please restate the feasibility claim as applying to the softened problem, or prove Conjecture 6 and show the exact-LP claim.","section":"Abstract and Sec. 6, Conjecture 6"},{"comment":"The proof of Lemma 4 is a single paragraph invoking [17, Prop. 2.7.1]. Two assertions are load-bearing and are not demonstrated: (i) that full dimension n of the fundamental polytope implies strict concavity of the SDLPD2 objective, and (ii) that suitable closed intervals for each variable can be defined from λ so that the unconstrained coordinate maxima are attained. Without strict concavity, Proposition 2.7.1 yields only that every limit point is stationary, not that the limit is the global maximum of SDLPD2. Please provide a detailed proof or a precise reference for the strict-concavity implication and the bounded-domain construction.","section":"Sec. C, Proof of Lemma 4"},{"comment":"The simulations use 'Decoding Algorithm 1 with update rule Lemma 5', i.e., the hard-min interval update in the κ→∞ limit. This is precisely the regime covered only by Conjecture 6, not by the proven Lemma 4 convergence result. The finite-κ update of Lemma 3, whose convergence is proven, is not simulated. The text should state explicitly that the simulated decoder is a conjectured limiting version of the algorithm, and it would be informative to include finite-κ results for comparison.","section":"Sec. 8, Simulation Results"},{"comment":"The decision rule that recovers the pseudo-codeword support from the dual solution assumes a solution of the exact DLPD2. For a finite-κ solution of SDLPD2, the relationship between the soft-min dual variables and the primal pseudo-codeword is not established; in particular, the hard-min inequalities used in the decision rule need not hold at a soft-min solution. This should be clarified, since the practical decoding procedure must specify how a bit decision is obtained from the variables produced by the convergent finite-κ algorithm.","section":"Sec. 6, decision rule"}],"minor_comments":[{"comment":"There are several typographical errors: 'belive' in the introduction, 'of of a random variable' in Sec. 5, and the inconsistent spelling 'SDLDP2' in Sec. 5 where SDLPD2 is meant.","section":"Throughout"},{"comment":"The notation in the proof and figure is inconsistent with the definitions: the quantities are defined as T'_{j,0} and T'_{j,1}, but the proof and Figure 4 use T'_{i,0} and T'_{i,1}. Please standardize the indices.","section":"Sec. D, Proof of Lemma 5 and Fig. 4"},{"comment":"The stepsize sequence is first called μℓ in the update rule and then αℓ in the convergence sentence. Make the notation consistent and give the conditions on the stepsize sequence needed for the cited incremental subgradient convergence result.","section":"Sec. 7"},{"comment":"The simulation description lacks details on the update schedule, tie-breaking rule, stopping criterion, number of simulated frames, and confidence intervals. With a single code instance and no error bars, the figure is best described as a proof of concept.","section":"Sec. 8 and Fig. 3"},{"comment":"The statement that 'any interesting code has a parity-check matrix whose rows have Hamming weight at least 3' is inaccurate for important code families such as IRA codes, which commonly contain degree-2 rows. Please rephrase to avoid overclaiming.","section":"Footnote 4"}],"recommendation":"major_revision","confidential_remarks":"The paper is honest about its main gap: the exact-LP feasibility claim rests on Conjecture 6. In my view the gap is fixable within the manuscript's scope by reframing the claims around the softened problem and clearly marking the κ→∞ limit as conjectural. The editor may also wish to check whether the simulation section should be expanded, since the current figure is a thin proof-of-concept for an unproven limiting update."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nRead the Vontobel-Koetter LP decoding paper. The main new thing is the dual LP formulation and the coordinate-ascent update rules derived from it. Lemma 3's closed-form update is genuinely useful: it shows the soft-min dual can be maximized with per-edge computations that look like sum-product message passing, and the kappa-to-infinity version (Lemma 5) gives an interval update that looks like min-sum. That connection is new relative to Yang et al. and Feldman et al., and it is worked out carefully. The paper also deserves credit for being explicit about what is proven and what is not.\n\nThe soft spots are real but the paper mostly knows about them. Lemma 4's proof of convergence for finite kappa is terse: the strict concavity assertion is plausible, but the argument that the global objective is strictly concave on the feasible set is compressed into a remark about full-dimensional fundamental polytope. A referee will want that expanded. The bigger gap is the abstract's claim that LP solvers with min-sum-like complexity are feasible. What is actually proven is convergence to the maximum of the softened SDLPD2 for fixed kappa. The exact LP optimum as kappa goes to infinity is Conjecture 6, and Sec. E shows a simple concave piecewise-linear function where coordinate ascent stalls at a suboptimal point. That example does not disprove Conjecture 6, but it kills the idea that the standard concave-convergence argument carries over. So the strong reading of the abstract is not established. The title says \"towards,\" so the gap is more a framing issue than a hidden flaw.\n\nSimulation results are thin: one code, no error bars, only a min-sum comparison. Fine as a proof of concept, not as a performance claim. Self-citations are appropriate and not load-bearing.\n\nBottom line: the dual derivation and the message-passing connection are solid and worth refereeing. The exact LP convergence claim needs either a proof of Conjecture 6 or a more careful statement of what the algorithm actually solves. I would send it to review, expecting the revision to either prove or prominently soften that claim.","headline":"Solid dual derivation and message-passing connection for LP decoding, with the exact-LP convergence claim honestly flagged as a conjecture rather than proven.","tokens_in":14328,"tokens_out":2857,"would_cite":true,"duration_ms":26797,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"pith_extraction":{"msc":["94B35","90C25"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper claims that LP decoding of LDPC codes can be done with message-passing complexity by applying coordinate ascent to a softened dual LP.","keywords":["linear-programming decoding","LDPC codes","dual linear program","coordinate ascent","min-sum algorithm","sum-product algorithm","soft-minimum operator","message passing"],"falsifier":"Run cyclic coordinate ascent on SDLPD2 at a fixed finite $\\kappa$ on a (3,6)-regular LDPC code and compare the dual objective it reaches with the global maximum obtained from a general-purpose convex solver; any reproducible gap would contradict Lemma 4. Alternatively, exhibit a parity-check matrix with no weight-1 or weight-2 rows whose softened dual objective is not strictly concave, or give a counterexample to Conjecture 6 in which the $\\kappa\\to+\\infty$ interval updates fail to reach the LP optimum.","tokens_in":13469,"feed_emoji":"📡","tokens_out":9961,"duration_ms":82087,"temperature":0.7,"pith_summary":"This paper argues that the linear program used in LP decoding of LDPC codes has enough structure that it can be solved with per-edge complexity comparable to message-passing decoding, rather than by calling a generic LP solver. The authors formulate the dual of the LP decoder and replace its ordinary minima by a soft-minimum operator, obtaining a concave objective (SDLPD2) that coordinate ascent can maximize. Their main convergence result, Lemma 4, says that cyclic coordinate ascent reaches the maximum of SDLPD2 for any finite softening parameter κ whenever the parity-check matrix has no rows of weight 1 or 2, and each update is computed by sum-product-style message passing. In the κ→∞ limit the update rules become interval-based and min-sum-like, but convergence to the exact LP optimum is left as Conjecture 6. Simulations on a [1000,500] (3,6)-regular LDPC code show the proposed algorithm performing near min-sum decoding, supporting the complexity claim.","feed_headline":"LP decoding of LDPC codes can run at message-passing speed","feed_subtitle":"A softened dual LP turns decoding into coordinate-ascent updates almost identical to min-sum and sum-product algorithms.","key_machinery":"The carrying object is the softened dual linear program SDLPD2, obtained by replacing each minimum in the dual DLPD2 with the soft-minimum operator $\\min^{(\\kappa)}_\\ell z_\\ell = -\\frac{1}{\\kappa}\\log\\bigl(\\sum_\\ell e^{-\\kappa z_\\ell}\\bigr)$, where $\\kappa$ acts as an inverse temperature. For finite $\\kappa$ this makes the dual objective concave and smooth, so block coordinate ascent applies. The mechanism that carries the argument is Lemma 3's closed-form edge update, in which the new dual variable $u'_{i,j}$ is half the difference between a variable-side soft-min message $(S'_{i,0}-S'_{i,1})$ and a check-side soft-min message $(T'_{j,0}-T'_{j,1})$; these differences are exactly the quantities that sum-product message passing computes. Cyclic application of this update is a Gauss-Seidel-style iteration whose convergence to the SDLPD2 optimum is Lemma 4. In the hard limit the soft minima become ordinary minima and the update rule becomes the min-sum algorithm, with the convergence gap captured by Conjecture 6.","core_discovery":"The paper's central claim is that LP decoding—usually presented as a call to a general-purpose LP solver—can be reformulated as the dual linear program DLPD2, and that a softened version of that dual, SDLPD2, can be maximized by coordinate ascent with updates of the same per-edge complexity as belief propagation. Lemma 4 proves convergence of cyclically updated coordinate ascent to the global maximum of SDLPD2, assuming the parity-check matrix has no rows of Hamming weight 1 or 2; the proof invokes the fundamental polytope (the intersection of the per-check convex hulls) having full dimension n, which yields strict concavity of the softened objective. The edge update is the closed form $u'_{i,j} = \\frac{1}{2}\\bigl((S'_{i,0}-S'_{i,1}) - (T'_{j,0}-T'_{j,1})\\bigr)$, where the $S$ and $T$ terms are soft minima over the local variable and check polytopes and can be evaluated with sum-product message passing. In the hard limit $\\kappa\\to+\\infty$ the update becomes min-sum-like, but the paper only conjectures (Conjecture 6) that the resulting interval-valued coordinate ascent still reaches the LP optimum. Thus the proven contribution is a message-passing-complexity decoder that provably solves the softened dual, with the exact LP decoder as the conjectured limit.","pith_inferences":["Because convergence is proven for every finite $\\kappa$ but the exact LP optimum is only conjectured at $\\kappa\\to\\infty$, a practical decoder would run at finite temperature; tracking the dual objective as $\\kappa$ grows would give a computable measure of how far the softened decoder is from true LP decoding.","The paper's note that its softened dual is close to the Bethe free energy suggests that Algorithm 1 is effectively a convex surrogate for belief propagation; if so, its provable convergence may extend to settings where sum-product decoding is known to oscillate.","The same softened-dual coordinate-ascent template could be applied to other structured linear programs—for example, compressed-sensing or 1-bit decoding problems—where the constraint polytope factors into many small local polytopes.","Changing the edge update schedule (randomized, parallel, or tree-based) is a natural testable extension; the Gauss-Seidel proof leaves room for schedules that improve convergence speed without changing the per-update complexity."],"forward_implications":["A decoder can provably reach the maximum of the softened dual SDLPD2 at any finite inverse temperature $\\kappa$, with per-edge work comparable to one sum-product message update.","The same update rules, with soft minima replaced by ordinary minima, coincide with min-sum-style operations and reproduce the experienced performance of min-sum decoding in simulations.","The exact LP-decoding optimum is recovered only in the $\\kappa\\to+\\infty$ limit, and that recovery rests on Conjecture 6 rather than on a proven convergence theorem.","Because any dual feasible point of DLPD2 yields a lower bound on the minimal AWGNC pseudo-weight of a parity-check matrix, the iterative updates can contribute to code analysis even before an exact LP solution is reached.","The proposed algorithms are hardware-friendly in principle: they use local, message-passing-like arithmetic and do not require a general LP solver."],"supporting_citations":[{"why":"introduces the LP decoder and the polytope constraints that this paper reformulates as PLPD2 and dualizes","marker":"[2]"},{"why":"provides the original LP-decoding formulation and motivation for the primal relaxation","marker":"[1]"},{"why":"supplies the factor-graph and sum-product message-passing machinery used to compute the update differences in Lemma 3 and to compare complexity","marker":"[11]"},{"why":"provides the linear-programming duality theory used to derive the dual DLPD2 from PLPD2","marker":"[14]"},{"why":"contains the block coordinate-ascent (nonlinear Gauss-Seidel) convergence proposition invoked in the proof of Lemma 4","marker":"[17]"},{"why":"supplies convergence guarantees for the incremental subgradient method that becomes Decoding Algorithm 2","marker":"[22]"},{"why":"establishes the earlier observed relationship between LP decoding and min-sum decoding that the coordinate-ascent updates exploit","marker":"[5]"}],"fun_headline_variants":["LP decoding gets message-passing speed via dual reformulation","Coordinate ascent on softened dual LP matches belief propagation complexity","Softened dual LP decoding matches sum-product complexity","From LP to message passing: a dual ascent shortcut","LP decoding made practical: dual coordinate ascent"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The proof of Lemma 4 assumes the softened dual objective is strictly concave and that each coordinate update has a unique maximizer, properties the paper asserts rather than demonstrates in detail, and the exact LP limit additionally rests on an unproven conjecture about interval-valued coordinate ascent.","fun_headline_variants_meta":{"raw":{"variants":["LP decoding gets message-passing speed via dual reformulation","Coordinate ascent on softened dual LP matches belief propagation complexity","Softened dual LP decoding matches sum-product complexity","From LP to message passing: a dual ascent shortcut","LP decoding made practical: dual coordinate ascent"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000538,"raw_usage":{"total_tokens":2598,"prompt_tokens":980,"completion_tokens":1618,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":596,"completion_tokens_details":{"reasoning_tokens":1544}},"tokens_in":596,"tokens_out":1618,"duration_ms":12386,"temperature":1.0,"reasoning_tokens":1544,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-28T19:52:29.703039+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run cyclic coordinate ascent on SDLPD2 at a fixed finite $\\kappa$ on a (3,6)-regular LDPC code and compare the dual objective it reaches with the global maximum obtained from a general-purpose convex solver; any reproducible gap would contradict Lemma 4. Alternatively, exhibit a parity-check matrix with no weight-1 or weight-2 rows whose softened dual objective is not strictly concave, or give a counterexample to Conjecture 6 in which the $\\kappa\\to+\\infty$ interval updates fail to reach the LP optimum.","supporting_citations":[{"cited_title":"Using lin ear programming to decode binary linear codes,","cited_arxiv_id":null,"evidence_quote":"introduces the LP decoder and the polytope constraints that this paper reformulates as PLPD2 and dualizes"},{"cited_title":"Feldman, Decoding Error-Correcting Codes via Linear Programming","cited_arxiv_id":null,"evidence_quote":"provides the original LP-decoding formulation and motivation for the primal relaxation"},{"cited_title":"Fact or graphs and the sum-product algorithm,","cited_arxiv_id":null,"evidence_quote":"supplies the factor-graph and sum-product message-passing machinery used to compute the update differences in Lemma 3 and to compare complexity"},{"cited_title":"Bertsimas and J","cited_arxiv_id":null,"evidence_quote":"provides the linear-programming duality theory used to derive the dual DLPD2 from PLPD2"},{"cited_title":"Bertsekas, Nonlinear Programming","cited_arxiv_id":null,"evidence_quote":"contains the block coordinate-ascent (nonlinear Gauss-Seidel) convergence proposition invoked in the proof of Lemma 4"},{"cited_title":"Nedi´ c, Subgradient Methods for Convex Minimization","cited_arxiv_id":null,"evidence_quote":"supplies convergence guarantees for the incremental subgradient method that becomes Decoding Algorithm 2"},{"cited_title":"On the relationship between lin- ear programming decoding and min-sum algorithm decoding,","cited_arxiv_id":null,"evidence_quote":"establishes the earlier observed relationship between LP decoding and min-sum decoding that the coordinate-ascent updates exploit"}],"review_version":1}