REVIEW 3 major objections 4 minor 37 references
Optimal Reconstruction Codes with Given Reads in Multiple Burst-Substitutions Channels
T0 review · 3 major / 4 minor · reviewed 2026-08-07 · deepseek-v4-flash
Pith's one-line read 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 = ε+ρ+λ.
desk verdict 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. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
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.
What would settle it
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)$.
Extended reading notes
Core claim
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)$.
Load-bearing premise
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$.
Editorial extensions
If this is right
- 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)$.
Reading between the lines
- 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.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
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.
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 (3)
- [Section 5.1, Theorem 5.1] 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 5.3, Theorem 5.9] 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 5.3, Claim 5.10] 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.
minor comments (4)
- [Theorem 5.1 proof] 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 6, Claim 6.2 proof] 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.
- [Appendix, Algorithm 2] 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.
- [Throughout] 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.
Circularity Check
No significant circularity: the main list-size trade-off is proved from independent ball-size, Johnson-type, and Kleitman-type bounds; the t-1 = epsilon + rho + lambda identity is bookkeeping, not a fitted prediction.
full rationale
The paper's central claims derive from self-contained combinatorial arguments rather than from quantities defined in terms of the target results. The ball-size estimates in Theorem 3.1 are obtained by direct counting of disjoint bursts. Theorem 4.9's redundancy/read trade-off is proved by separate lower and upper bounds: the lower bound uses a structural argument showing that small reconstruction degree forces a burst-correcting code, and the upper bound bounds intersection sizes via the sufficient-burst-pattern counting of Theorem 4.5; neither assumes the redundancy formula it proves. Theorem 5.12's L_asy(h)=h rests on an existential lower bound from Theorem 5.2 (via Kahn's theorem) and a universal upper bound from Theorem 5.9 (via the Kleitman-type diametric theorem, Theorem 5.8, and the Johnson-type bound, Theorem 5.1). These ingredients are independent of the target list-size asymptotics. The headline identity t-1 = epsilon + rho + lambda is a parameterization: with epsilon = t-s-1, rho = s-h, and lambda = h, the sum is t-1 by definition; the paper's contribution is proving that every such split is achievable in the exponent, not deriving the identity from the results. Self-citations by the authors appear only in related-work surveys and as context; they are not load-bearing in the proofs, and the main external tools [8, 19, 25] are independent. Conjecture 1 is explicitly flagged as open and is used only conditionally. The reviewer's concern about Claim 5.10, that a single burst interval J_l straddling I** could contribute two distinct bursts of v and hence the asserted counting implication may be under-justified, is a possible proof-gap or correctness issue in the upper-bound argument; it is not a circularity, since no equation is reduced to its own input or to a fitted parameter. Thus no circular step is exhibited.
Assumptions & free parameters
assumptions (4)
- standard math Kahn's large-matching theorem for r-uniform hypergraphs, quoted as Lemma 2.1 from [25].
- standard math Campos-Jenssen-Michelen-Sahasrabudhe independence-number theorem, quoted as Theorem 2.2 from [8].
- standard math Ahlswede-Khachatrian fixed-point property of coordinate shift operations, cited in Section 5.3.
- standard math Levenshtein's ball-intersection formula for Hamming balls, quoted as Equation (5) and attributed to [22].
Cite this review
Pith. "Pith review of Optimal Reconstruction Codes with Given Reads in Multiple Burst-Substitutions Channels." pith.science (2026). https://pith.science/paper/73K7OPTH
@misc{pith2026250612924,
author = {Pith},
title = {Pith review of: Optimal Reconstruction Codes with Given Reads in Multiple Burst-Substitutions Channels},
year = {2026},
howpublished = {\url{https://pith.science/paper/73K7OPTH}},
note = {Machine review of arXiv:2506.12924}
}
abstract
We study optimal reconstruction codes over the multiple-burst substitution channel. Our main contribution is establishing a trade-off between the error-correction capability of the code, the number of reads used in the reconstruction process, and the decoding list size. We show that over a channel that introduces at most $t$ bursts, we can use a length-$n$ code capable of correcting $\epsilon$ errors, with $\Theta(n^\rho)$ reads, and decoding with a list of size $O(n^\lambda)$, where $t-1=\epsilon+\rho+\lambda$. In the process of proving this, we establish sharp asymptotic bounds on the size of error balls in the burst metric. More precisely, we prove a Johnson-type lower bound via Kahn's Theorem on large matchings in hypergraphs, and an upper bound via a novel variant of Kleitman's Theorem under the burst metric, which might be of independent interest. Beyond this main trade-off, we derive several related results using a variety of combinatorial techniques. In particular, along with tools from recent advances in discrete geometry, we improve the classical Gilbert-Varshamov bound in the asymptotic regime for multiple bursts, and determine the minimum redundancy required for reconstruction codes with polynomially many reads. We also propose an efficient list-reconstruction algorithm that achieves the above guarantees, based on a majority-with-threshold decoding scheme.
Figures
Reference graph
Works this paper leans on
-
[1]
K. Abdel-Ghaffar, R. McEliece, A. Odlyzko, and H. van Tilborg. On the existence of optimum cyclic burst-correcting codes.IEEE Transactions on Information Theory, 32(6):768–775, 1986
work page 1986
-
[2]
K. A. Abdel-Ghaffar. On the existence of optimum cyclic burst correcting codes over GF(q). IEEE Transactions on Information Theory, 34(2):329–332, 1988
work page 1988
-
[3]
M. Abu-Sini and E. Yaakobi. On Levenshtein’s reconstruction problem under insertions, dele- tions, and substitutions.IEEE Transactions on Information Theory, 67(11):7132–7158, 2021
work page 2021
-
[4]
R. Ahlswede, N. Cai, and Z. Zhang. Diametric theorems in sequence spaces.Combinatorica, 12:1–17, 1992
work page 1992
-
[5]
R. Ahlswede and L. H. Khachatrian. The diametric theorem in Hamming spaces – optimal anticodes.Advances in Applied mathematics, 20(4):429–449, 1998
work page 1998
- [6]
-
[7]
K. Cai, H. M. Kiah, T. T. Nguyen, and E. Yaakobi. Coding for sequence reconstruction for single edits.IEEE Transactions on Information Theory, 68(1):66–79, 2021
work page 2021
- [8]
Show all 37 references
-
[9]
Y. M. Chee, H. M. Kiah, A. Vardy, V. K. Vu, and E. Yaakobi. Coding for racetrack memories. IEEE Transactions on Information Theory, 64(11):7094–7112, 2018
2018
-
[10]
Y. M. Chee and S. Ling. Constructions forq-ary constant-weight codes.IEEE Transactions on Information Theory, 53(1):135–146, 2006
2006
-
[11]
Z. Chen, P. Fan, and F. Jin. On the constructions of multiple-burst error-correcting codes. IEEE Transactions on Information Theory, 38(1):197–200, 1992
1992
-
[12]
T. Etzion. Constructions for perfect 2-burst-correcting codes.IEEE Transactions on Infor- mation Theory, 47(6):2553–2555, 2001
2001
-
[13]
Frankl and Z
P. Frankl and Z. F¨ uredi. The Erd˝ os-Ko-Rado theorem for integer sequences.SIAM Journal on Algebraic Discrete Methods, 1(4):376–381, 1980
1980
-
[14]
J. Gao, H. Liu, and Z. Xu. Stability through non-shadows.Combinatorica, 43(6):1125–1137, 2023
2023
-
[15]
Huang, O
H. Huang, O. Klurman, and C. Pohoata. On subsets of the hypercube with prescribed Ham- ming distances.Journal of Combinatorial Theory, Series A, 171:105156, 2020
2020
-
[16]
S. Jain, F. Farnoud, M. Schwartz, and J. Bruck. Coding for optimized writing rate in DNA storage. In2020 IEEE International Symposium on Information Theory (ISIT), pages 711–
-
[17]
Junnila, T
V. Junnila, T. Laihonen, and T. Lehtil¨ a. On Levenshtein’s channel and list size in information retrieval.IEEE Transactions on Information Theory, 67(6):3322–3341, 2021. 38
2021
-
[18]
Junnila, T
V. Junnila, T. Laihonen, and T. Lehtil¨ a. On unique error patterns in the Levenshtein’s sequence reconstruction model.IEEE Transactions on Information Theory, pages 1–1, 2025
2025
-
[19]
J. Kahn. A linear programming perspective on the Frankl-R¨ odl-Pippenger theorem.Random Structures & Algorithms, 8(2):149–157, 1996
1996
-
[20]
D. J. Kleitman. On a combinatorial conjecture of Erd˝ os.J. Combinatorial Theory, 1:209–214, 1966
1966
-
[21]
A. V. Kuznetsov and A. H. Vinck. A coding scheme for single peak-shift correction in (d, k)- constrained channels.IEEE Transactions on Information Theory, 39(4):1444–1450, 1993
1993
-
[22]
V. I. Levenshtein. Efficient reconstruction of sequences.IEEE Transactions on Information Theory, 47(1):2–22, 2001
2001
-
[23]
V. I. Levenshtein. Efficient reconstruction of sequences from their subsequences or superse- quences.Journal of Combinatorial Theory, Series A, 93(2):310–332, 2001
2001
-
[24]
V. I. Levenshtein and A. H. Vinck. Perfect (d, k)-codes capable of correcting single peak-shifts. IEEE Transactions on Information Theory, 39(2):656–662, 1993
1993
-
[25]
Liu and C
M. Liu and C. Shangguan. Approximate generalized Steiner systems and near-optimal constant weight codes.Journal of Combinatorial Theory, Series A, 209:105955, 2025
2025
-
[26]
F. J. MacWilliams and N. J. A. Sloane.The Theory of Error-Correcting Codes. North-Holland, 1978
1978
-
[27]
T. T. Nguyen, K. Cai, W. Song, and K. A. S. Immink. Optimal single chromosome-inversion correcting codes for data storage in live DNA. In2022 IEEE International Symposium on Information Theory (ISIT), pages 1791–1796. IEEE, 2022
2022
-
[28]
Sabary, H
O. Sabary, H. M. Kiah, P. H. Siegel, and E. Yaakobi. Survey for a decade of coding for DNA storage.IEEE Transactions on Molecular, Biological, and Multi-Scale Communications, 2024
2024
-
[29]
Sun and G
Y. Sun and G. Ge. Correcting two-deletion with a constant number of reads.IEEE Transac- tions on Information Theory, 69(5):2969–2982, 2023
2023
-
[30]
Y. Sun, Y. Xi, and G. Ge. Sequence reconstruction under single-burst-insertion/deletion/edit channel.IEEE Transactions on Information Theory, 69(7):4466–4483, 2023
2023
-
[31]
Van Overveld
W. Van Overveld. Multiple-burst error-correcting cyclic product codes.IEEE Transactions on Information Theory, 33(6):919–923, 1987
1987
-
[32]
Wei and M
H. Wei and M. Schwartz. Perfect codes correcting a single burst of limited-magnitude errors. IEEE Transactions on Information Theory, 69(2):951–962, 2022
2022
-
[33]
Wei and M
H. Wei and M. Schwartz. Sequence reconstruction for limited-magnitude errors.IEEE Trans- actions on Information Theory, 68(7):4422–4434, 2022
2022
-
[34]
Yaakobi and J
E. Yaakobi and J. Bruck. On the uncertainty of information retrieval in associative memories. IEEE Transactions on Information Theory, 65(4):2155–2165, 2019
2019
-
[35]
Z. Ye, X. Liu, X. Zhang, and G. Ge. Reconstruction of sequences distorted by two insertions. IEEE Transactions on Information Theory, 69(8):4977–4992, 2023. 39
2023
-
[36]
Yehezkeally and M
Y. Yehezkeally and M. Schwartz. Reconstruction codes for DNA sequences with uniform tandem-duplication errors.IEEE Transactions on Information Theory, 66(5):2658–2668, 2019
2019
-
[37]
Yehezkeally and M
Y. Yehezkeally and M. Schwartz. Uncertainty and reconstruction with list-decoding from uniform-tandem-duplication noise.IEEE Transactions on Information Theory, 67(7):4276– 4287, 2021. 40
2021
Reviewed August 7, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.