2025/06/15 by Wenjun Yu, Yubo Sun, Yu, Wenjun +7
Biochemistry, Genetics and Molecular Biology · Computer Science · #Advanced Data Storage Technologies #Algorithms and Data Compression #Combinatorics (math.CO) #DNA and Biological Computing #FOS: Computer and information sciences #FOS: Mathematics #Information Theory (cs.IT)
paper · pdf · doi:10.48550/arxiv.2506.12924
openalex publication_date 2025/06/15 · openalex created_date 2025/10/14 · openalex updated_date 2026/07/28
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 ε errors, with Θ(nρ) reads, and decoding with a list of size O(nλ), where t-1=ε+ρ+λ. 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.