{"id":"8cd9f5a1-de65-4d57-9f79-18e87467c238","arxiv_id":"2506.12924","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"For the multiple-burst substitution channel, the paper shows that error-correction capability, the read-count exponent, and the list-size exponent can be traded freely, with t-1 = epsilon + rho + lambda.","lead":"The paper proves a clean asymptotic trade-off for channels that corrupt data in up to t short bursts: a code that corrects only epsilon bursts, read Theta(n^rho) times, can be list-decoded with list size O(n^lambda), where t-1 = epsilon + rho + lambda. It also gives a fast majority-with-threshold algorithm, so the result is of direct use in DNA storage and racetrack-memory coding.","discovery_kind":"first_principles","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Proof of Theorem 5.9 relies on an unjustified counting step in Claim 5.10; if the claim fails, the upper bound L_asy(h) ≤ h collapses, so the central trade-off is not yet fully established.","rationale":"The paper's central contribution is the exponent trade-off t-1 = ε+ρ+λ with list size O(n^λ), captured by Theorem 5.12. The lower bound (Theorem 5.4) is built on the Johnson-type construction of Theorem 5.2 and is sound: the hypergraph matching argument, Claim 5.3, and the common-intersection argument all check out. The upper bound (Theorem 5.9) is the delicate part. The reader identified Theorem 5.8, the Kleitman-type diametric theorem, as the weakest assumption. After scrutiny, Theorem 5.8's proof appears essentially correct: the shift-to-fixed-point argument works for the cyclic burst metric (distances depend only on supports), the fiber decomposition in Case 1 is valid, and the asymptotic separation q^ℓ |Ball_{d-1,b}| < |Ball_{d,b}| holds because ℓ is constant and the ball sizes differ by a factor of Θ(n). Thus Theorem 5.8 is not the most acute problem. The genuinely fragile step is Claim 5.10 inside Theorem 5.9. The proof's counting claim that the union of v's bursts must intersect at least wt_b(v) of the bursts of x' is not generally true, because a single burst of x' can straddle the zeroed interval I** and create multiple bursts in v. The subsequent lower bound on wt_b(x'-e) also omits the contribution of the middle part w. These are not mere presentation issues: if the claim were false, the bound |S_u| = O(n^h) would fail and Theorem 5.12 would not follow. The claim is plausibly true by a different argument (comparing wt_b(x'-e) with 2 wt_b(v) - wt_b(x') + k), but the manuscript does not supply that argument. Therefore the proof of the central theorem has a real gap that needs to be closed. This does not change the overall conditional verdict: it strengthens the need for a revision, but does not, on the evidence available, warrant rejection.","tokens_in":34095,"tokens_out":34695,"duration_ms":364132,"concrete_test":"Independently verify Claim 5.10 by brute force for small parameters, e.g., q=2, b=2, t=4, s=2, h=1, n=12. Enumerate all e with wt_b(e)=3 and all x' with wt_b(x')≤4 and wt_b(x'-e)≤4; compute v by zeroing the (2,b)-extension of e's support; test whether any v has wt_b(v)≥3. If such an example exists, Claim 5.10 is false and the upper bound collapses. If none exists, replace the flawed counting step with a rigorous derivation of the claim and check that the rest of Theorem 5.9 holds.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The main trade-off Theorem 5.12 (L_asy(h) = h) depends on the upper bound Theorem 5.9, whose proof hinges on Claim 5.10. The claim states that after zeroing the (2,b)-extension I** of the bursts of e = y_j - y_i, any x' in the intersection of the two balls has burst weight wt_b(v) ≤ t-s+h-1. In the proof by contradiction, the paper asserts: \"By construction, K must intersect at least t-s+h intervals among J_1,...,J_w; otherwise, v would consist of at most t-s+h-1 bursts.\" This implication is not justified. A single burst J_l of x' (length ≤ b) can intersect several of the disjoint bursts K_i of v: if J_l straddles I**, zeroing I** splits it into pieces that belong to different K_i, so the number of K_i can exceed the number of J_l's intersecting their union. The subsequent inequality wt_b(x'-e) ≥ wt_b(v) + wt_b(z-e) also ignores the middle part w supported on I**\\I, which can bridge gaps and potentially reduce the burst count. Since Claim 5.10 is needed to apply Theorem 5.1 and obtain |S_u| = O(n^h), the upper bound L_asy(h) ≤ h is not rigorously proven at this step. The claim itself may be repairable via the weight-counting inequality wt_b(x'-e) ≥ 2 wt_b(v) - wt_b(x') + k ≥ t+1, but the manuscript does not provide this argument.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies reconstruction and list-reconstruction over the q-ary channel ch(t,b) that introduces at most t bursts of length at most b. The central contribution is Theorem 5.12, an asymptotic trade-off: if a code corrects ε=t-s-1 burst errors, one uses Θ(n^{s-h}) reads over ch(t,b), and the list size is Θ(n^h), so that t-1 = ε + ρ + λ with ρ=s-h and λ=h. The proof chain comprises sharp ball-size estimates for the burst metric, a redundancy equivalence for reconstruction codes (Theorem 4.9), an improved Gilbert-Varshamov bound via a recent discrete-geometry result (Theorem 4.10), a new Kleitman-type diametric theorem for the burst metric (Theorem 5.8), a Johnson-type upper bound (Theorem 5.1), a matching-based lower bound (Theorem 5.2), and a polynomial-time majority-with-threshold list-reconstruction algorithm.","tokens_in":34366,"tokens_out":52362,"duration_ms":658398,"significance":"If the main theorem is established, the paper gives a complete and clean asymptotic picture of the list-reconstruction trade-off for burst channels, subsuming the substitution and single-burst cases. The methods are of independent interest: the Kleitman-type theorem for the burst metric, the Johnson-type bounds via Kahn's theorem, and the improved GV bound are nontrivial contributions. The paper is honest about asymptotic statements, uses no fitted parameters, and all lower-bound constructions are explicit. The main risk is in the upper-bound chain, where several compression/zeroing steps are asserted without full justification.","major_comments":[{"comment":"The recursion A(n,2r+1,k) ≤ n(q^b-1)A(n-b,2r+1,k-1) is not justified. After deleting the common window x[i,i+b-1] from all codewords in C_{i,u}, the burst distance between two shortened vectors can decrease: the deleted coordinates, where both codewords agree, can separate bursts in the original vector, and their removal can bring the remaining support points closer together and merge bursts. Thus the punctured set is not necessarily a code with minimum burst distance 2r+1, and bounding it by A(n-b,2r+1,k-1) is unsupported. This theorem is load-bearing: it is applied in Theorem 5.9 and Corollary 5.11 to obtain the O(n^h) list-size upper bound. A correct proof must either preserve the minimum distance or replace the recursion with a variant that allows a bounded decrease in distance while keeping the same exponent w-r.","section":"Section 5.1, Theorem 5.1"},{"comment":"The assertion after defining S*_u that it \"is also a (t-s-1,b)-burst-correcting code\" is false as stated. Zeroing the interval I** can remove difference bursts between two codewords that are entirely contained in I**, so the pairwise burst distance can drop below 2(t-s-1)+1; two distinct codewords can even become identical after zeroing. Since this property is required for the application of Theorem 5.1 to bound |S_u|, this step needs a separate argument, for example a Johnson-type bound that holds for sets obtained by zeroing a constant-length interval, with the same exponent h.","section":"Section 5.3, Theorem 5.9"},{"comment":"The sentence \"By construction, K must intersect at least t-s+h intervals among J_1,...,J_w; otherwise, v would consist of at most t-s+h-1 bursts\" is too compressed. A naive reading is problematic because one interval J_l may intersect several K_i. The step can be justified by the minimality of wt_b(v): restricting the J_l's that intersect K to the complement of I** gives a decomposition of v into at most that many bursts, so the number of such J_l's is at least wt_b(v). This argument should be spelled out, as Claim 5.10 is a load-bearing step in the upper-bound proof.","section":"Section 5.3, Claim 5.10"}],"minor_comments":[{"comment":"The expression \"wt_b(x[i,i+b-1]) = k-1\" is ambiguous: it should refer to the burst weight of the complement x[i,i+b-1] after deleting the window, not to the window itself. Please clarify the notation.","section":"Theorem 5.1 proof"},{"comment":"The statement \"u[j] = z[j] for all j in [n]\\P\" is false on S; it should probably read \"for all j in P\". Please correct.","section":"Section 6, Claim 6.2 proof"},{"comment":"The algorithm appears to treat bursts on a linear array, but the paper works with cyclic intervals. A wrapping burst that contains both the beginning and the end of the sequence is not covered by starting positions in [p1-b+1, p1], so the claimed linear-time computation of the cyclic burst distance needs an explicit discussion of wrap-around.","section":"Appendix, Algorithm 2"},{"comment":"There are several typographical slips, e.g., \"Out list-reconstruction algorithm\" and inconsistent use of \"m(j)\" for both the arg max and the max value in Section 6. A careful proofreading pass is recommended.","section":"Throughout"}],"recommendation":"major_revision","confidential_remarks":"The stress-test concern about Claim 5.10 is real but repairable; the more serious issues are the puncturing/zeroing steps in Theorem 5.1 and Theorem 5.9, where the minimum-distance condition needed to apply the Johnson bound is not preserved. These are load-bearing for the central upper bound L_asy(h) ≤ h. The paper's high-level approach is sound and the results are likely correct, but the upper-bound chain needs a substantial repair or a different argument before the main theorem can be considered proven."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"What should you know: this is genuinely new work, and the lower bound and the Kleitman-type theorem are valuable. But the proof of the main list-size upper bound has a real gap.\n\nThe paper is the first to combine list decoding with reconstruction over burst-substitution channels. The trade-off t−1 = ε+ρ+λ is clean, and the lower bound (Theorem 5.4) is solid. The Kleitman-type diametric theorem for the burst metric (Theorem 5.8) and the Johnson-type bound via Kahn's theorem (Theorem 5.2) are reusable tools. The improved GV bound and the algorithmic section are also worthwhile.\n\nThe soft spot is in Section 5.3, Theorem 5.9, specifically Claim 5.10. The claim asserts that if wt_b(v) ≥ t−s+h, then the union of the K_i intervals must intersect at least t−s+h of the J_l intervals. That implication is not justified: a single J_l that straddles I** can split into pieces belonging to different K_i's, so the number of K_i's can exceed the number of J_l's it intersects. The subsequent inequality also ignores the middle term w, whose support lies on I**\\I and could bridge gaps, potentially reducing the burst count of the sum. This step is load-bearing: without Claim 5.10, the upper bound L_asy(h) ≤ h is not rigorously proven. The lower bound survives, but the equality in Theorem 5.12 is only as solid as this claim.\n\nThe gap may be repairable—the weight-counting inequality mentioned in the stress test looks plausible—but the manuscript does not provide that argument. This is a proof gap, not a counterexample.\n\nMinor issues: the abstract says \"optimal\" while the redundancy constant is only pinned down up to a factor of two, and the refined GV bound relies on an unreviewed preprint. Both are minor compared with the Claim 5.10 issue.\n\nWho this is for: coding theorists working on reconstruction, burst errors, and list decoding. The Kleitman-type theorem alone is of independent interest to combinatorialists.\n\nRecommendation: send it to peer review. It deserves serious referee time, but the referee must be told to check Claim 5.10 carefully. If the authors can supply a correct proof of that claim, the paper is a strong candidate for acceptance.","headline":"A strong new paper on list-reconstruction for burst channels, but the upper-bound proof has a gap in Claim 5.10 that needs to be fixed before the main trade-off is fully established.","tokens_in":34937,"tokens_out":5413,"would_cite":true,"duration_ms":58288,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["94B25","94B35","05D05","05C65"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper proves an exact burst-channel trade-off: a code correcting ε bursts, read Θ(n^ρ) times, can be list-decoded with list size O(n^λ), with t−1 = ε+ρ+λ.","keywords":["burst-substitution channel","reconstruction codes","list decoding","burst metric","diametric theorem","Johnson bound","Gilbert-Varshamov bound","trade-off exponent"],"falsifier":"Exhibit, for any fixed $q,b,d$ and infinitely many $n$, a set $A \\subseteq \\Sigma_q^n$ with burst-diameter $2d$ and $|A| > |\\mathrm{Ball}_{d,b}(0)|$; equivalently, at the code level, find a $(t-s-1,b)$-burst-correcting code and a read set of size $\\Theta(n^{s-h})$ whose list-reconstruction size is $\\omega(n^h)$.","tokens_in":33860,"feed_emoji":"📡","tokens_out":8278,"duration_ms":164916,"temperature":0.7,"pith_summary":"The paper aims to establish the exact asymptotic trade-off among error-correction power, number of reads, and decoder list size for channels that substitute at most $t$ bursts of length at most $b$. Its central result is that a length-$n$ code correcting only $\\epsilon$ bursts, when read $\\Theta(n^\\rho)$ times, can be list-decoded with list size $O(n^\\lambda)$, and this is optimal: $t-1 = \\epsilon+\\rho+\\lambda$. A sympathetic reader should care because this converts an apparently complicated bursty channel into a simple budget identity, and it shows that codes designed to correct far fewer bursts than the channel can inflict are still usable if one is willing to read the sequence several times and accept a small list. Along the way the paper proves sharp asymptotic bounds on burst-ball sizes, a diametric theorem for the burst metric, and an improved Gilbert-Varshamov bound for multiple bursts.","feed_headline":"t-1 = ε + ρ + λ: the burst-channel budget identity","feed_subtitle":"More reads mean a smaller list; the paper proves the exact exponent trade-off and shows it cannot be beaten.","key_machinery":"The load-bearing object is the burst metric $d_b(x,y)$: the minimum number of bursts of length at most $b$ needed to transform $x$ into $y$, whose balls have size $\\Theta(n^t)$ for fixed $t,b$. The upper bound on list size rides on a diametric theorem for this metric: any set of strings whose burst diameter is at most $2d$ has size at most $|\\mathrm{Ball}_{d,b}(0)|$, proved by a shifting argument that pushes sets to a fixed point and uses the asymptotic separation $q^\\ell|\\mathrm{Ball}_{d-1,b}(0)| < |\\mathrm{Ball}_{d,b}(0)|$. The matching lower bound uses a Johnson-type bound obtained from a theorem on large matchings in hypergraphs, giving $(r,b)$-burst-correcting codes inside a ball of radius $w$ with size $\\Omega(n^{w-r})$. The improved Gilbert-Varshamov bound is powered by a recent independent-set bound that applies when the joint degree of the auxiliary graph is much smaller than its maximum degree. Finally, the efficient algorithm uses a majority-with-threshold rule that creates only $O(1)$ 'joker' positions, then exhaustively fills them and applies a black-box list decoder for a weaker channel.","core_discovery":"The paper's core discovery is the asymptotic list-size exponent for reconstruction codes over the multiple burst-substitution channel $\\mathrm{ch}(t,b)$. For any $(t-s-1,b)$-burst-correcting code used when the channel introduces up to $t$ bursts, the minimal number of reads needed for unique reconstruction is $\\Theta(n^s)$, and if the number of reads is reduced to $\\Theta(n^{s-h})$, the best possible list size grows as $n^{(1-o(1))h}$ and at most $O(n^h)$; hence the asymptotic exponent is exactly $L_{\\mathrm{asy}}(h)=h$. Reparameterized, the paper proves the budget identity $t-1 = \\epsilon+\\rho+\\lambda$: over a channel with at most $t$ bursts, a code correcting $\\epsilon$ bursts, read $\\Theta(n^\\rho)$ times, can be list-decoded with list size $O(n^\\lambda)$, with $\\epsilon,\\rho,\\lambda$ non-negative integers. The upper bound is obtained from a new diametric theorem for the burst metric (the largest set of strings with burst-diameter at most $2d$ is a burst ball of radius $d$), together with a Johnson-type bound showing the existence of burst-correcting codes inside a ball whose size matches the upper bound. As corollaries, the paper determines the asymptotic redundancy of optimal reconstruction codes with $\\Theta(n^s)$ reads as that of $(t-s-1,b)$-burst-correcting codes, and improves the Gilbert-Varshamov bound for multiple bursts to $2t\\log_q n - \\log_q \\log n + O(1)$.","pith_inferences":["The identity $t-1 = \\epsilon+\\rho+\\lambda$ reads as a conservation law for reconstruction problems: each unit of the channel's error budget buys exactly one unit of correction, one unit of read-exponent, or one unit of list-exponent. The same balance may hold for other structured channels (insertions/deletions, tandem duplications) once sharp ball-size asymptotics are known; the paper itself only ","The diametric theorem for the burst metric is stated for its use here, but it is a standalone extremal statement: it identifies burst balls as the largest diameter-bounded sets in a non-Hamming metric, and could serve as an anticode bound for other burst-like metrics, such as limited-magnitude bursts.","The improved Gilbert-Varshamov bound removes a log factor by exploiting that ball intersections are an order of magnitude smaller than balls; analogous improvements may exist for any metric where intersection sizes drop by one polynomial degree."],"forward_implications":["A code built to correct only $t-s-1$ bursts, used over a channel that makes $t$ bursts, uniquely reconstructs with $\\Theta(n^s)$ reads; this is optimal, since any code that uniquely reconstructs with $o(n^{s+1})$ reads must itself be $(t-s-1,b)$-burst-correcting.","Reducing reads to $\\Theta(n^{s-h})$ forces list size $\\Theta(n^h)$: the exponent $h$ is both necessary and sufficient for every $(t-s-1,b)$-burst-correcting code.","The budget identity $t-1 = \\epsilon+\\rho+\\lambda$ lets the designer distribute the channel's burst budget arbitrarily among correction capability, number of reads, and list size, with no hidden loss in the exponent.","The asymptotic redundancy of optimal reconstruction codes with $\\Theta(n^s)$ reads equals that of $(t-s-1,b)$-burst-correcting codes, so known single-burst-correcting codes can be reused for multiple bursts at the cost of polynomially many reads.","There is a polynomial-time list-reconstruction algorithm achieving these guarantees whenever the code admits a list decoder for the weaker channel $\\mathrm{ch}(t-s+h,b)$."],"supporting_citations":[{"why":"defines the reconstruction problem and gives the ball-intersection formula for substitution channels that the burst trade-off generalizes.","marker":"[22]"},{"why":"supplies the hypergraph matching theorem used to construct large burst-correcting codes inside a ball (the Johnson-type lower bound).","marker":"[19]"},{"why":"provides the classical diametric theorem in Hamming space that the burst-metric version extends.","marker":"[20]"},{"why":"gives the q-ary diametric theorem used as the model for the burst-metric diametric theorem.","marker":"[4]"},{"why":"provides the independent-set bound with joint-degree control used to improve the Gilbert-Varshamov bound.","marker":"[8]"},{"why":"supplies the hypergraph matching lemma (large matchings with small codegree) used in the lower-bound construction.","marker":"[25]"},{"why":"gives the Johnson bound for constant-weight burst-correcting codes that Theorem 5.1 sharpens.","marker":"[10]"}],"fun_headline_variants":["Burst-channel budget: t-1 = ε + ρ + λ","Optimal burst codes: reads vs list-size trade-off","Exact exponent trade-off for burst-substitution channels","t-1 = ε+ρ+λ: the burst reconstruction identity","More reads, smaller lists: the burst-channel law"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The whole upper bound collapses if the diametric theorem for the burst metric fails—that is, if some set of strings with pairwise burst distances at most $2d$ can be larger than a burst ball of radius $d$.","fun_headline_variants_meta":{"raw":{"variants":["Burst-channel budget: t-1 = ε + ρ + λ","Optimal burst codes: reads vs list-size trade-off","Exact exponent trade-off for burst-substitution channels","t-1 = ε+ρ+λ: the burst reconstruction identity","More reads, smaller lists: the burst-channel law"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00036,"raw_usage":{"total_tokens":2044,"prompt_tokens":1140,"completion_tokens":904,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":756,"completion_tokens_details":{"reasoning_tokens":819}},"tokens_in":756,"tokens_out":904,"duration_ms":10435,"temperature":1.0,"reasoning_tokens":819,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T00:40:53.515228+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Exhibit, for any fixed $q,b,d$ and infinitely many $n$, a set $A \\subseteq \\Sigma_q^n$ with burst-diameter $2d$ and $|A| > |\\mathrm{Ball}_{d,b}(0)|$; equivalently, at the code level, find a $(t-s-1,b)$-burst-correcting code and a read set of size $\\Theta(n^{s-h})$ whose list-reconstruction size is $\\omega(n^h)$.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"defines the reconstruction problem and gives the ball-intersection formula for substitution channels that the burst trade-off generalizes."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"supplies the hypergraph matching theorem used to construct large burst-correcting codes inside a ball (the Johnson-type lower bound)."},{"cited_title":"Ahlswede, N","cited_arxiv_id":null,"evidence_quote":"gives the q-ary diametric theorem used as the model for the burst-metric diametric theorem."},{"cited_title":"Liu and C","cited_arxiv_id":null,"evidence_quote":"supplies the hypergraph matching lemma (large matchings with small codegree) used in the lower-bound construction."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"gives the Johnson bound for constant-weight burst-correcting codes that Theorem 5.1 sharpens."}],"review_version":1}