{"id":"658f7c0e-bff1-4ad7-af39-5f091258b054","arxiv_id":"2506.12193","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"For every small eta, explicit binary linear list-decodable codes correct an eta fraction of insertions and deletions with rate 1-O(eta^(1/4)) and polynomial-time encoding and decoding.","lead":"New binary linear codes, when decoding may return a list, can correct a small fraction of insertions and deletions while using almost all of their length for information. This breaks the rate 1/2 barrier that limits ordinary linear deletion-correcting codes.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Central claim hinges on whether Theorem 17's list-recovery parameter matches Definition 3; a convention mismatch would collapse the rate.","rationale":"The reader identified the import of Theorem 17 as the weakest assumption, and I agree that this external dependency is the most load-bearing part of the central claim. My concern is sharper than a mere constants issue: a mismatch between the paper's Definition 3 (disagreement fraction) and the source theorem's convention (agreement fraction) would invalidate the outer-code application and make the rate claim false. I checked the internal sync-matrix lemmas and the decoding argument; apart from minor typesetting issues in Lemma 15 and a small gap about window coverage for blocks shifted by insertions, the proof is coherent. The window-coverage issue is not fatal: blocks whose starts fall outside the original grid consume at least b edits each, so the total number of lost blocks (bad or grid-missed) remains bounded by gamma*n through the edit budget. Thus the central construction survives if and only if Theorem 17 is imported with the correct convention. A direct verification of [18, Theorem A.1] would settle the matter, so I recommend keeping the conditional verdict rather than accepting or rejecting outright.","tokens_in":11756,"tokens_out":50875,"duration_ms":590562,"concrete_test":"Check [18, Theorem A.1] and determine whether epsilon is the disagreement or agreement fraction; then re-run the Section 5 instantiation accordingly and see if the outer-code rate still approaches 1.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"Section 5 instantiates the external list-recoverable code from [18, Theorem A.1] with epsilon = 2*gamma and asserts that this yields an F2-linear (2*gamma, l0, L0)-list recoverable code under Definition 3, where alpha is the maximum disagreement fraction. The decoding argument in Theorem 18 guarantees only about (1 - 2*gamma)*n agreements, i.e., at most about 2*gamma*n disagreements. If [18] uses the standard list-recovery convention in which epsilon is the minimum agreement fraction (codewords must agree with the input lists on at least epsilon*N positions), then Theorem 17 with epsilon = 2*gamma would only certify list recoverability from agreement >= 2*gamma, i.e., disagreement up to 1 - 2*gamma, which is far weaker than what the decoder needs. In that case the outer code would need epsilon ≈ 1 - 2*gamma, making its rate 1 - O(sqrt(1 - 2*gamma)), a constant, and the claimed rate 1 - O(eta^{1/4}) would fail. The rest of the construction, including Lemma 15 and the sync-matrix argument, is internally coherent; the decisive unknown is the exact convention and parameter dependencies of the imported theorem.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper constructs explicit binary linear codes that are list-decodable from a fraction η of edit errors with rate 1-O(η^{1/4}) and list size exp(exp(exp(O_η(log* n)))). The construction concatenates an outer high-rate list-recoverable code (from Hemenway–Ron-Zewi–Wootters) with an inner 'sync matrix sequence': each outer symbol is encoded by a distinct linear map S_i, and the matrices are chosen so that any received window can be attributed to only a few blocks, while each block is itself a list-decodable linear code. The decoder scans windows, fills candidate boxes, prunes oversized boxes, and invokes outer list recovery. If the cited outer codes use the same convention as Definition 3, the main theorem gives the first rate-1 linear list-decodable insdel codes, breaking the unique-decoding half-rate barrier for linear edit correction.","tokens_in":11972,"tokens_out":42958,"duration_ms":474694,"significance":"This is a strong theoretical contribution. The sync-matrix construction is novel, the code is fully explicit, the encoder and decoder are polynomial-time, and the list size is sub-polynomial for fixed η. The result would be a substantial advance over the half-Singleton bound for linear edit-correcting codes, and the paper clearly explains the intuition behind the construction. The machine-checkable parts are not present, but the proofs are largely self-contained except for the imported list-recoverable code theorem.","major_comments":[{"comment":"The stated success probability in Lemma 15 is not derived. In the proof of Condition 1, the display following Eq. (1) gives Pr[1) fails] ≤ n^{l+1} 2^{(δ-1)b+l+2} ≤ n^{l+1} 2^{-0.5b+l+2}. With b ≥ 4(l+1) log n, this is 2^{l+2} n^{-(l+1)}, which for large n is much larger than the claimed n^{-(l+1)2^{l+2}}; the final inequality is algebraically false. A valid bound is O(n^{-(l+1)}) plus the 2n^{-7} term, which is still <1 for sufficiently large n and therefore suffices for the existence argument in Corollary 16, but the lemma as stated must be corrected.","section":"§4.1, Lemma 15"},{"comment":"The correctness of the outer list-recovery step depends on Theorem 17 being (ε,l0,L0)-list recoverable in the sense of Definition 3, i.e., at most ε fraction of disagreements. The manuscript quotes Theorem 17 without stating the convention used in [18]. If [18] uses the alternative agreement-fraction convention (codewords must agree with the input lists on at least εN positions), then instantiating ε=2γ would guarantee only agreement ≥2γ, which is far weaker than the (1-2γ) agreement needed in Theorem 18, and the main rate claim would collapse. The authors must state the convention explicitly and confirm that the parameter match is with Definition 3.","section":"§5, instantiation of Theorem 17"}],"minor_comments":[{"comment":"The definition of L is garbled by the binomial-coefficient typesetting; it should read L = 2^{2/ε+1}, as used in the proof.","section":"§3, Lemma 11"},{"comment":"The phrase 'Take b and 2^{l+1} to be the n and ϵ in Lemma 11' appears to be a typo: to obtain L = 2^{l+2} one must take ε = 2/(l+1), not ε = 2^{l+1}.","section":"§4, Lemma 13 proof"},{"comment":"The definition of l0 is typeset as inom{L(γ)}{γ^3}; it should be ⌈L(γ)/γ^3⌉ (a ceiling), as used in the proof of Theorem 18.","section":"§5, parameter l0"},{"comment":"References [8] and [19] both refer to the same paper by Guruswami and Wang; one of the two citations should be removed or replaced.","section":"References"}],"recommendation":"major_revision","confidential_remarks":"The central construction and proof strategy appear sound, and the main technical error (Lemma 15's probability bound) is fixable without changing the main theorem. The more delicate point is the unstated convention in the imported list-recoverable code theorem; if the convention is disagreement-fraction, the proof works as written, but the paper must say so explicitly and verify against the source. I recommend major revision rather than rejection because the concerns are local and addressable."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nThe headline: this paper claims to break the rate-1/2 barrier for linear edit-correcting codes in the list-decoding regime, with rate 1-O(eta^{1/4}) and polynomial-time encoding/decoding. The construction is genuinely new: sync matrix sequences, an inner code with l-wise intersection-free row spaces, and concatenation with a high-rate list-recoverable outer code. The random linear list-decoding lemma (Lemma 11) is also a nice standalone contribution. If the main theorem holds, it's a major advance in the field.\n\nThe paper does good work: the sync condition and the counting argument for the boxes are coherent, and the proof structure is mostly clear. Lemma 15's failure exponent is misstated (the proof gives a weaker bound), but the typo is patchable. Also, the abstract says 'any eta > 0' while Theorem 19 restricts to eta < 1/64 - minor misalignment.\n\nThe real soft spot is the import of Theorem 17. The paper's Definition 3 is in terms of maximum disagreement (alpha). Theorem 17 is stated as an (epsilon,l0,L0)-list-recoverable code, but the paper never states which list-recovery convention [18] uses. If [18] uses the standard agreement convention (epsilon = minimum agreement fraction), then instantiating with epsilon=2*gamma gives only list recoverability from 2*gamma agreement, i.e., up to 1-2*gamma disagreement - the opposite direction from what the decoder needs. To get the needed 2*gamma-max-disagreement guarantee via the agreement convention, you'd need epsilon approx 1-2*gamma, which makes the outer rate 1-O(sqrt(1-2*gamma)) = constant, and the rate 1-O(eta^{1/4}) claim collapses. I can't resolve this from the text; the authors must state [18]'s definition and confirm the parameter direction. Until then, the central theorem is not established.\n\nThere's also small stuff: the list size exp(exp(exp(O_eta(log* n)))) is far from practical, and the rate is far from capacity, but those are tradeoffs, not flaws.\n\nWho is this for: researchers working on insertion/deletion codes, especially linear codes; it's a theory paper with clear open questions. It deserves a serious referee - the construction is clever and the question is central. But the referee must check the [18] convention and, if necessary, fix the instantiation. My suspicion is the convention mismatch is real, but that's exactly what peer review should catch.\n\nRecommendation: send to peer review, but flag the convention issue prominently. If it's resolved, this could be a strong IT paper.","headline":"A clever construction that may break the rate-1/2 barrier for linear list-decoding of edits, but a likely list-recovery convention mismatch in the imported theorem puts the central claim in doubt.","tokens_in":12542,"tokens_out":11650,"would_cite":false,"duration_ms":122910,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["94B05","94B35","94B65"],"pacs":[],"model":"deepseek-v4-flash","headline":"For any small fraction $\\eta$ of insertions and deletions, there is a linear list decodable code with rate $1-O(\\eta^{1/4})$ and polynomial-time encoding and decoding.","keywords":["list decoding","edit-correcting codes","insertions and deletions","linear codes","code concatenation","list-recoverable codes","sync matrix sequences","small-bias distributions"],"falsifier":"Take a small explicit instance (e.g., $n=2^6$, $\\gamma=1/8$, so $\\eta=1/64$), build the generator matrix, and run a randomized search over adversarial edit patterns of weight at most $\\eta b n$; the theorem is false if any pattern yields a received string with more than $L_0$ codewords within edit distance, or if the decoder's output list omits the original codeword.","tokens_in":11542,"feed_emoji":"🛡️","tokens_out":16766,"duration_ms":164931,"temperature":0.7,"pith_summary":"The paper asks whether the rate ceiling $1/2$ for linear codes that uniquely correct even one deletion is an inherent limit of linearity or only of unique decoding. It answers by constructing linear list decodable codes: for any fixed small fraction $\\eta$ of insertions and deletions, there is a linear code of length $n$ correcting an $\\eta$ fraction of edits with rate $1-O(\\eta^{1/4})$ and list size $\\exp(\\exp(\\exp(O_\\eta(\\log^* n))))$. The encoder and decoder run in polynomial time, and the construction is deterministic. This shows that allowing a list of possible outcomes, rather than demanding a unique answer, lets linear codes use almost all their length for information even in the presence of edit errors.","feed_headline":"Linear list codes correct edits with rate approaching 1","feed_subtitle":"Linear codes can now correct edit errors while packing almost all their length with information.","key_machinery":"The central object is a $(\\delta,l,L)$-sync sequence: matrices $S_1,\\dots,S_n \\in F_2^{a\\times b}$ with full row rank such that the edit-distance balls $B(\\operatorname{Row} S_{k_i}\\setminus\\{0\\}, \\delta b)$ of any $l+1$ distinct row spaces are disjoint, and each $S_i$ is itself $(\\delta,L)$-list decodable. This condition generalizes the natural alignability condition that row spaces be pairwise disjoint, which has rate at most $1/2$; by instead requiring only that any $l+1$ row spaces have disjoint edit balls, the inner-code rate becomes $a/b = 1 - 2/(l+1) - 5H(\\delta)$, approaching $1$ as $l$ increases. The construction of sync sequences uses a small-bias generator applied to $(l+1)$-wise independent seeds, with a Vazirani XOR-Lemma argument showing that the failure probability is polynomially small, and a polynomial-time verification procedure makes the construction deterministic. The sequence is the load-bearing mechanism that lets the decoder align received blocks to at most $l$ positions and bound the number of candidates per box before outer list recovery.","core_discovery":"The central claim is that linear list decodable codes can correct a fraction of insertions and deletions with rate approaching $1$, breaking the $1/2$ rate barrier that holds for unique linear edit correction. The proof works by a two-level concatenation: an outer $F_2$-linear list-recoverable code of rate $1 - c_1\\sqrt{2\\gamma}$ is folded to alphabet size $2^a$, and each symbol $c'_i$ is then encoded as $c'_i S_i$ using a $(\\delta,l,L)$-sync sequence of matrices $S_i \\in F_2^{a\\times b}$. The sync condition, which says that the edit-distance balls of the row spaces of any $l+1$ distinct matrices are disjoint, replaces the stricter pairwise-disjointness condition that would force inner rate at most $1/2$; with the relaxed condition the inner rate is $a/b \\geq 1 - 2/(l+1) - 5H(\\delta)$, which approaches $1$ as $l$ grows. The decoder scans length-$b$ windows of the received string, inserts all plausible inner symbols into boxes, truncates boxes that grew too large, and then runs the outer list-recovery algorithm, producing a list that provably contains the transmitted codeword. The theorem states that for $0<\\eta<1/64$ the resulting rate is $1-O(\\eta^{1/4})$ with the stated triple-exponential list size.","pith_inferences":["A natural next step is to determine the optimal tradeoff for linear list-decodable edit codes; the paper's rate $1-O(\\eta^{1/4})$ may not be tight, and a matching lower bound would be a natural extension.","The sync-matrix technique is not specific to insertions and deletions; the same relaxed-intersection idea could be adapted to other channels where unique linear decoding has a rate barrier, such as burst errors or tandem duplications.","If an outer list-recoverable code with rate $1-O(\\varepsilon)$ and list size polynomial in $1/\\varepsilon$ were found, the same concatenation would yield linear list-decodable edit codes with rate $1-O(\\eta^{1/2})$ and poly-sized lists; the current triple-exponential list size is an artifact of the outer code, not of the sync-matrix construction.","The construction could be tested empirically at moderate block lengths to see how the actual rate and list size behave for finite $n$, since the hidden constants may be large before the asymptotics kick in."],"forward_implications":["For any fixed fraction of edits $\\eta$, the rate can be made arbitrarily close to $1$ by choosing $\\eta$ small, at the cost of larger list size and block length.","The half-Singleton bound $R \\leq (1-\\delta)/2$ for linear codes applies only to unique decoding; with list decoding the rate can be $1-O(\\eta^{1/4})$ even when correcting an $\\eta$ fraction of edits.","The encoder and decoder are polynomial-time and deterministic, so the gain in rate does not require random coding or super-polynomial decoding effort.","The outer list-recoverable code is the bottleneck for the list size; improving that building block would immediately improve the list-size exponent of the final code.","The construction is fully linear over $F_2$, so the code can be represented by a generator matrix and combined with other linear operations such as linear network coding."],"supporting_citations":[{"why":"Derives the rate $\\leq 1/2$ lower bound for linear codes correcting one deletion, the barrier this paper breaks via list decoding.","marker":"[4]"},{"why":"Supplies the explicit small-bias generator used to build the sync matrix sequences in Lemma 15.","marker":"[14]"},{"why":"Provides the Vazirani XOR lemma that bounds the statistical distance of small-bias distributions, used in the sync-sequence probability analysis.","marker":"[15]"},{"why":"Gives list-decodability of random linear codes in Hamming metric, the source of Lemma 11 for the inner codes' $(\\delta,L)$-list decodability.","marker":"[16]"},{"why":"Provides the construction of $(l+1)$-wise independent random variables used as seeds for the sync matrices (Corollary 3.34).","marker":"[17]"},{"why":"Contains Theorem A.1, the outer $F_q$-linear list-recoverable code with rate $1-c_1\\sqrt{\\epsilon}$ and triple-exponential list size, which the main theorem imports.","marker":"[18]"},{"why":"Introduces the sliding-window decoding method that the inner decoder adapts for aligning received blocks to codeword positions.","marker":"[19]"}],"fun_headline_variants":["Linear list codes for edits reach rate approaching 1","Edit-correcting linear list codes break 1/2 rate ceiling","Rate-1 linear list codes beat 1/2 edit-correction limit","List decoding lets linear edit codes approach rate 1","Linear edit codes with list decoding: rate near 1"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that the external outer codes truly recover a message from a small list of candidate symbols at each position while losing only $O(\\sqrt{\\epsilon})$ of their rate; if their promised performance is weaker than claimed, the final rate and list size would change, though the concatenation strategy would survive.","fun_headline_variants_meta":{"raw":{"variants":["Linear list codes for edits reach rate approaching 1","Edit-correcting linear list codes break 1/2 rate ceiling","Rate-1 linear list codes beat 1/2 edit-correction limit","List decoding lets linear edit codes approach rate 1","Linear edit codes with list decoding: rate near 1"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000602,"raw_usage":{"total_tokens":2771,"prompt_tokens":866,"completion_tokens":1905,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":482,"completion_tokens_details":{"reasoning_tokens":1819}},"tokens_in":482,"tokens_out":1905,"duration_ms":17256,"temperature":1.0,"reasoning_tokens":1819,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T01:03:54.129895+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a small explicit instance (e.g., $n=2^6$, $\\gamma=1/8$, so $\\eta=1/64$), build the generator matrix, and run a randomized search over adversarial edit patterns of weight at most $\\eta b n$; the theorem is false if any pattern yields a received string with more than $L_0$ codewords within edit distance, or if the decoder's output list omits the original codeword.","supporting_citations":[{"cited_title":"On linear and cyclic codes for correcting deletions,","cited_arxiv_id":null,"evidence_quote":"Derives the rate $\\leq 1/2$ lower bound for linear codes correcting one deletion, the barrier this paper breaks via list decoding."},{"cited_title":"Simple constructions of almost k-wise independent random variables,","cited_arxiv_id":null,"evidence_quote":"Supplies the explicit small-bias generator used to build the sync matrix sequences in Lemma 15."},{"cited_title":"Three xor-lemmas—an exposition,","cited_arxiv_id":null,"evidence_quote":"Provides the Vazirani XOR lemma that bounds the statistical distance of small-bias distributions, used in the sync-sequence probability analysis."},{"cited_title":"On the list-decodability of random linear codes,","cited_arxiv_id":null,"evidence_quote":"Gives list-decodability of random linear codes in Hamming metric, the source of Lemma 11 for the inner codes' $(\\delta,L)$-list decodability."},{"cited_title":"Pseudorandomness,","cited_arxiv_id":null,"evidence_quote":"Provides the construction of $(l+1)$-wise independent random variables used as seeds for the sync matrices (Corollary 3.34)."},{"cited_title":"Local list recovery of high-rate tensor codes and applications,","cited_arxiv_id":null,"evidence_quote":"Contains Theorem A.1, the outer $F_q$-linear list-recoverable code with rate $1-c_1\\sqrt{\\epsilon}$ and triple-exponential list size, which the main theorem imports."},{"cited_title":"Deletion codes in the high-noise and high-rate regimes,","cited_arxiv_id":null,"evidence_quote":"Introduces the sliding-window decoding method that the inner decoder adapts for aligning received blocks to codeword positions."}],"review_version":1}