CS Paper Radar

Orbit Reduction and Learned Run Distributions for Finite-Blocklength Binary Deletion Channels

Hassan Khodaiemehr, Chen Feng

cs.IT ·submitted 2026-09-21 16:54 UTC · v2
theory

Abstract

In DNA data storage, racetrack memories, and packet networks, data are written as many short strands of fixed length. The receiver knows where each strand begins and ends, and deletions occur only inside a strand. The relevant limit for such systems is the block capacity $C_N(d)$, the largest mutual information between a length-$N$ input and the output of a binary deletion channel with deletion probability $d$. Because the boundaries are known, $C_N(d)/N$ is never smaller than the classical capacity $C(d)$. Computing $C_N(d)$ is hard because the input takes $2^N$ values. For $0\le d<1$, we show that the optimal input is unique, gives positive probability to every string, and is unchanged by complementing or reversing the strings. We then introduce the optimized run distribution (ORD), which assigns one probability to each number of runs; it is optimal for $N\le3$ and is solved with a numerical optimality certificate up to $N=16$. For longer strands, an exact recursion for the output distribution gives unbiased rate estimates, and an empirical Bernstein inequality turns them into confidence intervals. Within the statistical precision, a one-parameter Markov input performs as well as the best inputs found. For strands of 100-200 bits, known boundaries increase the rate by up to 0.026 bits per symbol beyond the best certified upper bound on the capacity of the unsegmented channel. Via Fano's inequality, the block capacity also bounds the rate of any code that uses a single strand; in the tabulated case, this bound is tighter than the best known finite-length bound for strands longer than about 90 bits. Conversely, block rates yield lower bounds on $C(d)$; at $d=0.1$, the bound is within $1.1\times10^{-4}$ bits/use of the best certified lower bound. Finally, InfoNCE estimates, even with the optimal critic, empirically lose most of their ability to rank inputs as the strand length grows.

Comment
13 pages, 4 figures, 9 tables. v2: corrected orbit reduction (complement-reversal theorem); ORD values recomputed with numerical certificates; nested Monte Carlo replaced by exact-marginal estimator with confidence intervals, new Fano single-strand converse and InfoNCE analysis

Closest papers

Nearest neighbours by meaning across the whole index.

Improved Lower Bounds on the Capacity of the Binary Deletion Channel via a Learning Approach to Run-Length Inputs

cs.IT ·2026-09-21 ·Hassan Khodaiemehr, Chen Feng, Tolga M. Duman
theory similarity 0.69
Abstract · 22 pages, 6 figures, 4 tables, 3 algorithms. v2: rigorous chain-penalty correction for the VTR bound, verified interval-arithmetic evaluatio…

The best constructive lower bounds on the capacity of the binary deletion channel come from random codes with independent run lengths, yet the two strongest such bounds, due to Drinea and Mitzenmacher and to Venkataramanan, Tatikonda, and Ramchandran, have been evaluated mainly for geometric or low-parameter run-length laws. We let a learning algorithm choose the run-length law freely, which raises three challenges. First, the Drinea-Mitzenmacher functional is an infinite sum over the ways deletions merge runs; we show that it depends on the law only through its mean, its full-deletion probability, and bilinear forms in the law and its renewal weights, so that gradients of truncations are exact and every truncation can only lower the bound. Second, for non-Markov inputs the output is no longer Markov and the Venkataramanan-Tatikonda-Ramchandran analysis breaks down; we show that the residual length of the current input run turns the output into a hidden Markov chain, which extends the bound to every finite-support law. Third, its correction term counts only output runs formed from three input runs; we prove a larger correction that accounts for every output run formed by several input runs, which improves the published bound even for truncated geometric laws. Certified by interval arithmetic, the new bounds exceed all previously published deterministic lower bounds at every tabulated deletion probability, by up to $6.86\times10^{-3}$ bits per channel use and 6.8%. At large deletion probability the learned laws concentrate on run-length clusters with survivor counts about two standard deviations apart, like a pulse-amplitude constellation.

0.43

A New Upper Bound on the Binary Deletion Channel Capacity

cs.IT ·2026-09-11 ·Özgür Soysal
theory similarity 0.65
Abstract

We prove that the capacity of the binary deletion channel satisfies $C(d)\le (1-d)/4$ for every $13/20\le d<1$. The proof describes the output from right to left, using a six-bit context to assign a description length. We bound the increase in expected description length minus output entropy when one input bit is added. A relative-entropy identity reduces this bound to finitely many linear inequalities. A potential on input windows of length 26 makes the inequalities telescope, giving a bound for every input word. Deletion composition extends the result from $d=13/20$ to all larger deletion probabilities. We also obtain finite-block bounds on mutual information and decoding error, with explicit $O(\log n/n)$ corrections. The finite certificate is checked using exact integer arithmetic, and the proof is formalized end to end in Lean.

0.34

Binary Deletion Channel Capacity to Within One Hundredth of a Bit

cs.IT ·2026-09-16 ·Dimitris Papailiopoulos
theorycode/datahighly cited similarity 0.62
Abstract · 122 pages. Source, exact certificate tables, and verification programs: https://github.com/anadim/binary-deletion-channel-capacity

The exact capacity of the binary deletion channel remains unknown despite decades of work on achievable rates and converse bounds. We establish a computer-assisted approximation whose error is below $0.0095$ bits per transmitted bit, uniformly over all deletion probabilities. The mean certified error bound, with uniform weighting of deletion probability, is below $0.006522$. The estimate is the midpoint of explicit lower and upper bounds. For the converse, a stationary-source reduction is combined with finite inequalities covering every allowed input configuration. Two constructions control the unobserved input beyond a finite window: one uses a common outside survivor sequence and bounds omitted deletion patterns, while the other cancels an entropy term to make outside probabilities enter linearly. For the lower bound, finite-state inputs combine output-entropy estimates with selected disjoint counts of compatible deletion masks; independent-run inputs retain additional uncertainty about output-run boundaries. Directed numerical checks establish the finite inequalities. An analytic comparison between deletion probabilities then extends the pointwise bounds over the entire parameter range. The lower endpoint supplies rates within $0.019$ bits of capacity in the asymptotic coding sense. We give the derivations, recorded computational costs, and complete numerical inputs and programs needed to verify the result.

0.61

Correcting Burst Errors with Applications to DNA-Based Data Storage

cs.IT ·2026-10-11 ·Yuan-Pon Chen, Olgica Milenkovic
theory similarity 0.61
Abstract · 19 pages, 2 figures, 3 tables

We introduce the problem of permutation burst error-correction, motivated by applications in molecular data storage with nanopore sequencing read platforms. A permutation burst of length $k$ is an error that affects a substring of length $k$ of a string of length $n$ by permuting its entries. Permutation burst errors can be corrected using classical burst error-correcting codes, such as Fire and Reed-Solomon codes. Here, we study how to reduce the redundancy of these classical codes by taking into account that the burst error preserves the weight of the substring. In addition, we further restrict our model to handle cyclic permutation bursts only, which are of independent practical and mathematical interest. Our main results include proving/establishing the following: a) for $k=o(\sqrt{n}),$ the redundancy of any permutation burst error correcting code is at least $\log n-k+\log \binom{2k-2}{k-2}+o(1).$ This result follows from McDiarmid's concentration bound; b) for $k \geq 9$ and $k=o\left(\sqrt{\frac{n}{\log n}}\right)$, the redundancy of any cyclic permutation burst error correcting code is at least $\log n +\log (k(k-1)-56)-\log\,80+o(1).$ c) the asymptotic redundancy upper bounds for the two types of substring errors that are twice the lower bound; d) constructions for both permutation burst and cyclic permutation burst errors that involve Varshamov-Tenegoltz type constraints or represent generalizations and extensions of Fire and other codes. In particular, we exhibit polynomially encodable and decodable codes that can correct cyclic bursts of length $\leq k$ using $\log n + k + 49\log k + O(\log \log k)$ redundant bits.

0.21

MacKay-Neal Codes for DNA Channels under Block-MAP Decoding

cs.IT ·2026-10-28 ·Kenta Kasai
theory similarity 0.59
Abstract · 14 pages

We prove achievability below the symmetric information rate (SIR) under block maximum a posteriori (MAP) decoding for a fixed-degree MacKay-Neal (MN) socket ensemble on the quaternary insertion-deletion-substitution channel used to model DNA reads. For every integer $\ell\ge4$, the $(\ell,3,3)$ socket ensemble, with one transmitted bit fixed and an independent uniform known offset, has limiting rate $r_\star=6/\ell$ bits per stored nucleotide. If the joint SIR $J_t$ of a fixed number $t$ of reads under independent, uniformly distributed input nucleotides exceeds $r_\star$, the ensemble-average full extended-word block error is $O(1/n)$, and deterministic graph-offset sequences attain the same limiting rate and message-average error bound. This result concerns the discrete rate family $6/\ell$, not arbitrary rates approaching a given SIR. The channel permits arbitrarily many insertions and unbounded drift, with no alignment supplied to the receiver. The proof combines established MN parity and distance estimates with a strict arbitrary-candidate-list bound and a list construction that accounts for hidden output boundaries.

0.26

The Generalized Random Access Problem for Linear Codes

cs.IT math.CO ·2026-08-20 ·Anina Gruica, Antonio Petrillo, Ferdinando Zullo
hot direction similarity 0.59
Abstract

Random access is a central requirement in DNA-based storage systems: one would like to recover selected information symbols without sequencing the whole encoded object. A recent combinatorial model associates to a generator matrix $G\in F_q^{k\times n}$ the random variable $τ_i(G)$, measuring the number of sampled columns needed to recover the information vector $e_i$. We study the cardinality-based extremal and finite-geometric aspects of simultaneous multi-symbol recovery. For a nonempty set $I\subseteq[k]$, let $τ_I(G)$ denote the number of random column samples needed until all vectors $e_i$, $i\in I$, lie in the span of the observed columns. This variable interpolates between the singleton random access problem and the full-recovery problem underlying coverage depth. For each $m$, we introduce uniform worst-case and average parameters over all requested sets $I$ with $|I|=m$. Using the known subset-counting formula for $E[τ_I(G)]$, we establish general upper and lower bounds for these parameters. In particular, the lower bounds are expressed through order statistics of the singleton recovery variables and specialize to the known singleton bounds when $m=1$. For systematic MDS encoders, we record an equivalent form of the known multi-symbol expectation formula and derive monotonicity and asymptotic consequences. For simplex encoders in arbitrary dimension, we obtain closed formulae in terms of Gaussian binomial coefficients; the full-recovery endpoint agrees with the known coverage-depth formula for simplex codes. Finally, in dimension three we study balanced quasi-arcs and compare their values with the simplex and MDS benchmarks.

0.49

Random Deletion for Circuits in Regular Matroids

cs.DS ·2026-10-24 ·Karthekeyan Chandrasekaran, Chandra Chekuri, Weihao Zhu
similarity 0.58
Abstract · 43 pages, 5 figures

We study a simple random deletion algorithm to find short circuits in regular matroids. Given a regular matroid $M$ with $m$ elements, the algorithm randomly deletes each element independently with probability $1-1/m^{Θ(1/g)}$ where $g$ is the size of a minimum circuit, and returns the remaining set $R$ of elements. We establish the following results: 1. With high probability, $R$ contains no circuit and is therefore independent. 2. For every $α$-approximate minimum circuit $C$ where $α\geq 1$, with probability at least $m^{-O(α)}$, the entire circuit $C$ survives in $R$ and moreover, the minimum number of elements that need to be removed to make $R$ independent is $O(α\log(α+2))$. This yields an algorithmic proof that the number of $α$-approximate minimum circuits is $m^{O(α)}$, improving the previous known bound of $m^{O(α^2)}$ by Gurjar and Vishnoi, and resolving a recent conjecture of Khanna, Putterman, and Song. Our results yield two immediate applications. First, we obtain very simple RNC algorithms for computing the shortest circuit, and for enumerating all $α$-approximate circuits, of a regular matroid without computing the Seymour decomposition. Second, we obtain a randomized parallel algorithm to find a basis of a regular matroid under independence-oracle access. It uses polynomially many independence-oracle queries in $O(\log m)$ adaptive rounds and succeeds with high probability. This follows from the framework of Khanna, Putterman, and Song and the improved counting bound, and extends their result from graphic matroids to regular matroids.

0.61

Weak arcs and applications to the DNA-based storage access problem

cs.IT math.CO ·2026-08-20 ·Geertrui Van de Voorde, Ferdinando Zullo
theory similarity 0.58
Abstract

Weak arcs are point sets in PG$(n-1,q)$ meeting every general hyperplane (those are the hyperplanes not going through one of the points given by the standard basis vectors) in at most $n-1$ points. In this paper, we study weak arcs together with balanced variants which are contained on the sides of the fundamental simplex. We give an upper bound on the size of weak arcs, characterise the largest balanced quasi-arcs in the plane and construct large balanced quasi-arcs in PG$(3, q)$. We then use these configurations to build point sets for the random-access problem in DNA-based storage. The constructions are explicit, work over small fields, and attain recovery expectations matching the best known asymptotic bounds.

0.33