{"id":"14c5c63b-2335-4844-b7da-79b33aa278a9","arxiv_id":"2502.07308","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"AEL expander amplification is shown to preserve a strengthened average-radius list decoding property with erasures, yielding explicit codes with constant alphabet and optimal list size near the generalized Singleton bound.","lead":"This paper constructs error-correcting codes from expander graphs that can be list decoded all the way to capacity using a purely combinatorial argument, without relying on algebraic structure. As a byproduct, it provides the first explicit LDPC codes that achieve list decoding capacity.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Corollary 3.7's inner-code rate ρ+ε/4 is inconsistent with its claimed (1−ρ, k, ε/2) erasure property; the final bound should be 1−ρ−5ε/4, not 1−ρ−ε.","rationale":"The reader's weakest_assumption identifies exactly the parameter mismatch in Corollary 3.7: the inner-code rate ρ+ε/4 is inconsistent with the claimed (1−ρ, k, ε/2) property. My independent check of the parameter flow confirms this: Corollary 4.3 gives (1−r) for rate r, so r=ρ+ε/4 yields δ0=1−ρ−ε/4, and Theorem 3.2 then produces a global bound of 1−ρ−5ε/4, not 1−ρ−ε. This is a concrete, verifiable flaw in the proof of the main existence theorem, and it is the single most load-bearing issue because the stated inequality is the paper's headline result. The flaw is not catastrophic: it is a constant-factor gap in ε that can be repaired by adjusting ρ_in or redefining ε, so the qualitative claim ('approaching the generalized Singleton bound') is likely salvageable. The algorithmic Section 5 inherits the same δ0, so the repair must be propagated there as well. I have not found a more serious flaw in the combinatorial or SoS arguments; the reader's conditional verdict is appropriate. My read does not change that verdict, hence UNCHANGED.","tokens_in":41415,"tokens_out":9311,"duration_ms":78331,"concrete_test":"Recompute Corollary 3.7 by substituting r_in = ρ+ε/4 into Corollary 4.3 to obtain δ0 = 1−ρ−ε/4, then applying Theorem 3.2. Check whether the displayed inequality ∑_{h∈H} Δ(g,h) ≥ (|H|−1)(1−ρ−ε) can be derived; the algebra gives (|H|−1)(1−ρ−5ε/4) instead. If the authors instead intend ρ_in = ρ/(1−ε/4), redo the substitution and verify the final bound after redefining the gap parameter.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The main existence theorem (Corollary 3.7, and informally Theorem 1.1) rests on instantiating Theorem 3.2 with an inner code Cin that is (1−ρ, k, ε/2) average-radius list decodable with erasures. The proof of Corollary 3.7 chooses Cin via Corollary 4.3 with rate ρ_in = ρ + ε/4. Corollary 4.3 states that a random linear code of rate r is (1−r, L, ε) average-radius list decodable with erasures. Therefore Cin is (1−ρ−ε/4, k, ε/2), not (1−ρ, k, ε/2). Applying Theorem 3.2 then yields CAEL is (1−ρ−ε/4, k, ε) average-radius list decodable with erasures, so the inequality in Corollary 3.7 becomes ∑ Δ ≥ (|H|−1)(1−ρ−5ε/4), not the claimed (|H|−1)(1−ρ−ε). The rate calculation ρ(CAEL) ≥ (1−ε/4)(ρ+ε/4) ≥ ρ is correct, but the gap parameter is off by ε/4. This is a genuine parameter mismatch in the proof of the central existence claim. The issue is repairable by choosing ρ_in = ρ/(1−ε/4) (or absorbing the loss into a redefined ε), but as written the corollary does not follow from the stated parameters. Because this mismatch affects the main theorem and propagates to the algorithmic corollary (Corollary 5.25), it is the most load-bearing concern.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper presents an expander-based construction of explicit codes approaching the relaxed generalized Singleton bound. The main combinatorial result (Theorem 3.2) shows that the Alon–Edmonds–Luby (AEL) distance amplification preserves a strong form of average-radius list decodability with erasures: if a constant-sized inner code is (δ0, k, ε/2) average-radius list decodable with erasures and the expander has sufficiently small second eigenvalue, then the AEL code is (δ0, k, ε) average-radius list decodable with erasures. The proof uses a partition of the list induced by local projections and an induction with erasures. The authors instantiate the inner code via random linear codes or folded Reed-Solomon codes, obtaining a family of codes with rate at least ρ, constant alphabet size, and list decoding up to radius (k−1)/k(1−ρ−ε). They also provide an SoS-based list decoding algorithm for these codes and observe that the construction inherits the LDPC property from the outer code.","tokens_in":41793,"tokens_out":23838,"duration_ms":187373,"significance":"The conceptual contribution is significant: it provides a non-algebraic, purely combinatorial route to capacity-approaching list decodable codes, and the AEL-based local-to-global argument is elegant and largely self-contained. If the parameter issues identified below are repaired, the result would give the first explicit LDPC codes achieving list decoding capacity, with an optimal O(1/ε) list size, and a new proof technique based on expander mixing and erasure-based induction rather than polynomial interpolation. The algorithmic extension via SoS is also a valuable contribution, though it relies on the same parameter instantiations. The main proof of Theorem 3.2 appears sound; the problems lie in the parameter matching when instantiating the theorem with known inner codes.","major_comments":[{"comment":"The instantiation of the inner code has a parameter mismatch. Corollary 4.3 guarantees that a random linear code of rate r is (1−r, L, ε) average-radius list decodable with erasures. The proof of Corollary 3.7 chooses r = ρ+ε/4 and then claims the inner code is (1−ρ, k, ε/2). This is inconsistent: the correct property is (1−ρ−ε/4, k, ε/2). Applying Theorem 3.2 with δ0 = 1−ρ−ε/4 yields an AEL code that is (1−ρ−ε/4, k, ε), so the final inequality becomes ∑_h Δ(g,h) ≥ (|H|−1)(1−ρ−5ε/4), not the claimed (|H|−1)(1−ρ−ε). To obtain the stated bound, the inner code rate should be ρin = ρ+ε (in the nontrivial regime ε < 1−ρ). Additionally, the choice ρin = ρ+ε/4 requires ρ+ε/4 ≤ 1, i.e., ε ≤ 4(1−ρ); for larger ε the proof needs a separate vacuous case, since the target bound is then non-positive. This mismatch affects Corollary 3.7, the informal Theorem 1.1, and Corollary 5.25.","section":"Corollary 3.7 and Theorem 1.1"},{"comment":"The union bound over subsets S is miscalculated. The displayed bound states 2^n κ ≤ 2^n · 2^{(10L/ε+1)·εn/2} · q^{−⌊εn/2⌋} ≥ 1 − 2^{-n/3} for q ≥ 2^{2/ε}·2^{10L/ε}. Substituting this q gives q^{−εn/2} = 2^{−(2+10L)n/2}, and the total exponent becomes n + (5L + ε/2)n − (1+5L)n = εn/2. Hence the bound is 2^{εn/2}, which grows with n and cannot be ≤ 2^{-n/3}. The argument can be repaired by taking a larger alphabet (roughly q ≥ 2^{(10L + 10/3)/ε}) or by a sharper count of subsets of size at most (1−ρ)n, but as written the proof does not establish the claimed probability bound. Since the existence of suitable inner codes is not in question, this is a repairable quantitative error, but it is load-bearing for the explicit construction via random linear codes.","section":"Corollary 4.3"}],"minor_comments":[{"comment":"The hypothesis of Claim 4.1 says that each punctured code CS is (1−ρ, L, ε/(1−s)) average-radius list decodable, but the proof uses the condition with 1−ρ(CS). Since ρ(CS) ≥ ρ, the stated hypothesis is stronger than what is verified in Corollary 4.3. The proof should be aligned with the statement.","section":"Claim 4.1"},{"comment":"The inequality (1−ε/4)(ρ+ε/4) ≥ ρ is asserted without qualification, but it holds only when ε ≤ 4(1−ρ). In the interesting regime where 1−ρ−ε > 0, this condition is automatically satisfied, so the claim is correct there, but the proof should mention the case split for ε ≥ 1−ρ.","section":"Corollary 3.7 (rate inequality)"},{"comment":"The phrase 'explicit inner codes' is used for codes obtained by searching over all linear codes of a constant length and rate. This is a standard convention for constant-sized objects, but it should be stated explicitly, since the inner code is not given by a deterministic formula. The alternative fully explicit choice via folded Reed-Solomon codes is mentioned but not used in the main corollary.","section":"Corollary 3.7 (explicitness)"},{"comment":"There are several typos that should be fixed: 'probablity' in the proof of Corollary 4.3; 'psueocodewords' in Definition 5.9; 'diffcult' in the discussion of distances in Section 5.1; and 'captuted' in the Introduction.","section":"Throughout"}],"recommendation":"major_revision","confidential_remarks":"The two major issues are localized parameter-matching errors rather than fundamental flaws: the induction proof of Theorem 3.2 is sound, and the qualitative claims are likely correct after adjusting constants and adding the vacuous-case split. I recommend major revision rather than rejection. I would also suggest that the authors double-check all union-bound calculations in the final version, as the Corollary 4.3 error is easy to miss."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things to know. First, this is the first explicit LDPC construction achieving list decoding capacity, and it gets there through a combinatorial local-to-global argument rather than algebra. That is a real result. Second, the paper as posted has a parameter hole in its main existence corollary. Corollary 3.7 uses an inner code of rate ρ+ε/4 and claims it is (1−ρ, k, ε/2) average-radius list decodable with erasures, but Corollary 4.3 only gives (1−rate, k, ε/2). So the instantiation actually yields (1−ρ−ε/4, k, ε/2), and applying Theorem 3.2 gives the final bound (|H|−1)(1−ρ−5ε/4) rather than (|H|−1)(1−ρ−ε). This is repairable by choosing ρ_in = ρ/(1−ε/4) or redefining ε to absorb the loss, but as written the central bound does not follow. The same incorrect instantiation is repeated in Corollary 5.25, so the algorithmic corollary inherits the issue.\n\nThe main theorem itself, Theorem 3.2, is the real contribution and it checks out. The inductive proof tracking partitions of local projections, treating common error locations as erasures, and applying expander mixing at the right places is careful and convincing. Lemmas 3.6 and 3.8 are clean, and the reduction to known inner codes is honest. I did not verify every step of the SoS section; it is dense and leans heavily on the framework from [JST23], but the structural result does not depend on the algorithmic part, which is good. The citation pattern is fine: the self-citations to [JST23] and [Sri24] are for the SoS machinery and are not circular.\n\nSoft spots, in proportion: the Corollary 3.7 parameter mismatch is real and load-bearing because it weakens the stated Singleton-gap guarantee, but it is localized and fixable. The algorithm section is harder to fully check, but nothing there looked obviously wrong. Minor: the abstract promises list size O(1/ε) while the formal statements fix k; that is standard and not a problem.\n\nThis paper is for coding theorists and for anyone interested in expander-based constructions. It deserves a serious referee: the main theorem is new, significant, and mostly clean, and the parameter error should be caught and repaired in revision. I would send it to review rather than desk-reject.","headline":"A genuinely new expander-based route to list-decoding capacity; the main local-to-global theorem is sound, but Corollary 3.7 has a real parameter mismatch that needs fixing.","tokens_in":42292,"tokens_out":2879,"would_cite":true,"duration_ms":27262,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["94B65","94B35","05C48"],"pacs":[],"model":"deepseek-v4-flash","headline":"Expander-based codes attain the ε-relaxed generalized Singleton bound with constant alphabet and optimal list size.","keywords":["list decoding","generalized Singleton bound","expander codes","AEL construction","average-radius list decoding","LDPC codes","sum-of-squares","explicit codes"],"falsifier":"Take any explicit code from the construction and search all received words g (or a sufficiently large random sample) for a list of k codewords whose average Hamming distance is below ((k−1)/k)(1−ρ−ε); the main theorem predicts that no such configuration exists, so any one would refute the claim.","tokens_in":41243,"feed_emoji":"🕸️","tokens_out":7323,"duration_ms":58963,"temperature":0.7,"pith_summary":"This paper claims that a single expander-based device—the Alon–Edmonds–Luby (AEL) distance amplification procedure—can transform any high-rate code into a code that meets the ε-relaxed generalized Singleton bound, not just the classical distance bound. Concretely, for every rate R, every ε>0, and every list size k, the paper constructs explicit codes over a constant alphabet with the property that for any received word g and any list H of at most k codewords, the average Hamming distance from g to the list is at least ((|H|-1)/|H|)(1−R−ε). Such codes can be list decoded up to radius (k−1)/k(1−R−ε) deterministically in time $n^{{O_{k,ε}}$(1)}. The proof is combinatorial and spectral, using expansion and a partition/erasure analysis of local projections instead of polynomial interpolation. As a corollary the paper obtains explicit LDPC codes achieving list decoding capacity.","feed_headline":"Expanders alone get codes to list-decoding capacity","feed_subtitle":"Constant alphabet, optimal list size, and the first explicit LDPC codes at capacity follow from one amplifier.","key_machinery":"The carrying object is the AEL construction: an (n,d,λ)-expander bipartite graph G, a constant-sized inner code Cin ⊆ Σ^d_in, and a high-rate outer code Cout; the codeword of Cout is written on the left vertices, spread across edges, and grouped again on right vertices. The proof mechanism is a local-to-global amplification for the stronger property of being average-radius list decodable with erasures. At each left vertex, the local projections of the k codewords induce a partition of the list; the expander mixing lemma guarantees a nontrivial partition τ on a δout n / k^k fraction of left vertices. The local average-distance inequality for Cin is applied to the parts of τ, while error locations common to all members of a part are treated as erasures and handled by induction on k, which converts the local inequalities into the global inequality. The decoding algorithm then replicates this proof inside a degree-t sum-of-squares relaxation, where pseudocodewords replace integral codewords and η-goodness controls pseudocovariance, yielding the generalized Singleton bound for the relaxation.","core_discovery":"The central claim is a local-to-global theorem: if the constant-sized inner code Cin used in the AEL construction is (δ0, k, ε/2) average-radius list decodable with erasures, and the bipartite expander has second eigenvalue λ ≤ δout/(6 k^k) ε, then the resulting AEL code is (δ0, k, ε) average-radius list decodable with erasures. The paper instantiates this with inner codes given by random linear codes (or, if full explicitness is required, folded Reed–Solomon codes) and with high-rate outer codes, producing for every ρ, ε, k an explicit family of rate ≥ρ codes over an alphabet of size $2^{{(k^k/ε)^{O(1)}}$} satisfying the ε-relaxed generalized Singleton bound. The same round of ideas is carried through a sum-of-squares relaxation, yielding a deterministic algorithm that list decodes up to radius (k−1)/k(1−ρ−ε) with a list of size at most k−1.","pith_inferences":["Editorial extension: the same 'common-error-locations become erasures' mechanism should transfer to interleaved codes and other graph products, where the complete bipartite graph case (λ=0) is already noted in the paper; one test is whether it yields list-recovery bounds for tensor products of arbitrary codes.","Editorial extension: the sum-of-squares proof shows the generalized Singleton bound is certified by a convex relaxation, not only by integral combinatorics; this suggests other spectral decoding bounds, such as Johnson-type radii, might be relaxed the same way.","Editorial extension: since the outer code only needs high rate, constant distance, and unique decodability, the construction may compose with any near-MDS or expander-based outer family, potentially giving linear-time encodable and decodable capacity-approaching codes with different tradeoffs."],"forward_implications":["For any fixed list size k, the bound forces every ball of radius (k−1)/k(1−R−ε) to contain at most k−1 codewords; choosing k=O(1/ε) gives list size O(1/ε) at list-decoding capacity.","The construction yields explicit LDPC codes—codes given by parity checks of size 2^{(1/ε)^{O(1)}}—that achieve list decoding capacity, which were previously known only through random constructions.","No polynomial interpolation or algebraic geometry is used: the entire list-size bound follows from expansion and the partition/erasure argument, so any high-rate outer code with constant distance, e.g. LDPC or Tanner codes, can be amplified.","The decoding algorithm runs in deterministic time n^{2^{O(k^{4k}/ε^{10})}}, with the list size at most k−1, for any received word and any radius up to (k−1)/k(1−R−ε)."],"supporting_citations":[{"why":"Supplies the distance amplification construction that the paper generalizes to list decoding.","marker":"[AEL95]"},{"why":"Gives the random linear inner codes that are average-radius list decodable with erasures.","marker":"[AGL24b]"},{"why":"Provides fully explicit folded Reed–Solomon inner codes with the same average-radius property.","marker":"[CZ24]"},{"why":"Supplies the sum-of-squares proof-to-algorithm framework for list decoding AEL codes.","marker":"[JST23]"},{"why":"Yields the infinite families of Ramanujan-based (n,d,λ) expanders used in the construction.","marker":"[LPS88]"},{"why":"Provides the Tanner-code construction of the high-rate outer code with constant distance.","marker":"[GRS23]"},{"why":"Gives the unique decoder for expander codes used as a subroutine in the final algorithm.","marker":"[Zém01]"}],"fun_headline_variants":["Expanders yield explicit codes at list-decoding capacity","List-decoding capacity with expanders, no algebra","Generalized Singleton bound via simple expanders","First explicit LDPC codes at capacity from expanders"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The conclusion is conditional on the existence of a constant-sized inner code that is (1−ρ, k, ε/2) average-radius list decodable with erasures at essentially the target distance; if no such code exists with the stated alphabet, rate, and slack, the claimed final parameters must be weakened to match the inner code actually available.","fun_headline_variants_meta":{"raw":{"variants":["Expanders yield explicit codes at list-decoding capacity","List-decoding capacity with expanders, no algebra","Generalized Singleton bound via simple expanders","First explicit LDPC codes at capacity from expanders"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000221,"raw_usage":{"total_tokens":1546,"prompt_tokens":1139,"completion_tokens":407,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":755,"completion_tokens_details":{"reasoning_tokens":345}},"tokens_in":755,"tokens_out":407,"duration_ms":3963,"temperature":1.0,"reasoning_tokens":345,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-08T13:09:56.715172+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take any explicit code from the construction and search all received words g (or a sufficiently large random sample) for a list of k codewords whose average Hamming distance is below ((k−1)/k)(1−ρ−ε); the main theorem predicts that no such configuration exists, so any one would refute the claim.","supporting_citations":[],"review_version":1}