CS Paper Radar

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

Hassan Khodaiemehr, Chen Feng, Tolga M. Duman

cs.IT ·submitted 2026-09-21 17:11 UTC · v2
theory

Abstract

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.

Comment
22 pages, 6 figures, 4 tables, 3 algorithms. v2: rigorous chain-penalty correction for the VTR bound, verified interval-arithmetic evaluation of all bounds, complete proofs, and a reorganized presentation

Closest papers

Nearest neighbours by meaning across the whole index.

Binary Deletion Channel Capacity to Within One Hundredth of a Bit

cs.IT ·2026-09-16 ·Dimitris Papailiopoulos
theorycode/datahighly cited similarity 0.74
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

A New Upper Bound on the Binary Deletion Channel Capacity

cs.IT ·2026-09-11 ·Özgür Soysal
theory similarity 0.71
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

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

cs.IT ·2026-09-21 ·Hassan Khodaiemehr, Chen Feng
theory similarity 0.69
Abstract · 13 pages, 4 figures, 9 tables. v2: corrected orbit reduction (complement-reversal theorem); ORD values recomputed with numerical certificate…

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.

0.24

Maximal input entropy for binary two-deletion and two-insertion channels

cs.IT cs.FLmath.CO ·2026-10-31 ·Haobo Ma, Wenlin Zhang
similarity 0.60
Abstract · 12 pages; exact enumeration code, outputs and Lean companion in ancillary files

Under uniform transmission, we determine the received binary words that maximize input entropy for two-deletion and two-insertion channels. For two deletions the maximizers are exactly the two alternating words at every positive received length. For two insertions the same conclusion holds from received length five onward; we give all smaller cases and exact maximal values. The proof combines an embedding-count identity organized by runs with strict convexity estimates, and a grouping of two-position deletion masks. For every insertion radius we give the complete positive embedding histogram of an alternating received word. We also determine its three-deletion histogram for every length, and certify all three-deletion maximizers through received length twelve and all three-insertion maximizers through length eighteen by exact integer comparison. These computations give precise three-error conjectures with their small-length exceptions.

0.12

Why Forget-Only Unlearning Needs Memorization

cs.LG cs.ITstat.ML ·2026-10-07 ·Luka Radić, Vikrant Singhal, Amartya Sanyal
similarity 0.58
Abstract

Machine unlearning asks for a deletion algorithm whose output is close to retraining from scratch without the selected forget examples. In this work, we study forget-only unlearning, where the deletion algorithm receives only the trained model and the examples to forget, with no retained data or extra training information. We ask whether forget-only unlearning is always possible. We first show that this depends on the learning method: different datasets can produce the same trained model but require very different outputs after the same examples are removed. Using this observation, we derive lower bounds on how accurately unlearning can match retraining and instantiate them for several standard learning algorithms. We then ask what must be true when forget-only unlearning succeeds. To this end, we derive lower bounds on what an algorithm must memorize about the training data to handle arbitrary deletion requests. For simple threshold learners, the required information can be as large as the entire dataset, even though ordinary training keeps only one boundary point. Overall, our results show that information discarded during ordinary learning may be needed later for deletion, so models designed for forget-only unlearning may need to retain more information than standard training does.

0.18

Capacity of a Mixed Multiple-Access Channel with Causal Observation

cs.IT ·2026-09-18 ·Xianwei Meng
similarity 0.58
Abstract

We determine the capacity region of a mixed binary multiple-access channel whose receiver can choose how each observation is formed. Two ports reveal the sum modulo two of the transmitted symbols with retention probabilities $\pg>\pb$; their roles are interchanged by an unknown state that remains fixed during the block. With one observation per channel use, no transmitter feedback, and zero switching cost, the region is $R_1+R_2\le\pg$ for every fixed error threshold below one, and a strong converse holds. For error thresholds below one half, the largest open-loop sum rate is $(\pg+\pb)/2$, whereas a fixed port permits only $\pb$. A causal receiver attains the larger region by learning the state from erasure flags while using every channel use for data. A posterior port rule makes only finitely many incorrect selections almost surely, with a uniformly bounded expected number of mistakes. Exact random linear-code formulas and output-counting converses quantify the finite-block consequences. At blocklength 256 with $(\pg,\pb)=(0.9,0.4)$, independent numerical validation supports 214 message bits at a one-percent ensemble failure target, compared with 148 bits for the best open-loop allocation in the same code ensemble. The resulting 44.59\% increase is achieved with the same transmission and observation budgets. The analysis exhibits an explicit capacity gain from controlling the observation axis and separates that gain from information lost after a record has already been formed.

0.23

Exponentially Larger Deletion-Correcting Codes and Constant-List-Decodable Insertion-Deletion Codes

cs.IT ·2026-09-18 ·Han Mao Kiah, Hengjia Wei, Ruixiao Zeng
theory similarity 0.58
Abstract · 46 pages, 7 figures

We establish improved asymptotic rate bounds for adversarial insertion--deletion codes. For binary unique-deletion correction in the linear-deletion regime, we strictly improve Levenshtein's classical lower-bound expression. At deletion fraction $δ=0.1$, our achievable rate increases from $0.162009$ to $0.194890$, a relative gain of approximately $20.30\%$. For list decoding with any prescribed finite list size $L$, we obtain new achievable-rate bounds for binary deletion and insertion codes. Our approach combines the Lovász local lemma with refined counting of common subsequences and supersequences, using generating functions and run-restricted sampling. We also establish a combinatorial reduction that trades $L$ units of insertion budget for one unit of deletion budget without changing the code or increasing the list size. It transfers insertion lower bounds at $γ+Lδ$ and deletion upper bounds at $δ+γ/L$ to mixed errors. We also derive a run-counting Levenshtein-type list-decoding upper bound and a higher-order Elias-type upper bound. The latter recovers Yasunaga's asymptotic unique-decoding bound at $L=1$ and strictly improves the Haeupler--Shahrasbi--Sudan insertion upper bound for every fixed $L$ and $0<γ<q-1$. Numerical comparisons quantify the gains and the remaining gaps.

0.41

An Upper Bound to the Undetected Error Exponent with Erasure Decoding at Positive Rates

cs.IT ·2026-10-11 ·Seyed AmirPouya Moeini, Marco Dalai, Albert Guillén i Fàbregas
theory similarity 0.58
Abstract

We study the undetected-error exponent of discrete memoryless channels with erasure decoding. Assuming that the undetected-error and erasure probabilities vanish, we derive an upper bound on the undetected-error exponent at positive rates. The bound uses Somekh-Baruch's genie-aided argument where an auxiliary output provides the decoder with a list of codewords. It recovers Telatar's tight rate-zero converse and is at least as tight as the straight-line bound. A numerical example shows that the improvement over the straight-line bound can be strict.

0.16