Lower bounds improve understanding of error correction with deletions
Lower Bounds for all List-Decodable Deletion Codes
Information TheoryDiscrete Mathematics
Summary
When some bits of data are accidentally deleted, it can be hard to know what the original message was. This paper studies codes that allow you to find a small list of possible original messages after some deletions. The authors show new limits on how large such codes can be to still work well, improving previous results and extending them to more cases. They also analyze how many common pieces two sequences can share after deletions or insertions.
What this means in practice
- •For data storage engineers: Determine theoretical limits on code sizes for recovering data after multiple deletions in storage devices.
- •For communication system designers: Use bounds to assess feasibility of list decoding schemes for reliable transmissions with deleted bits.
A theory result. No direct application yet.
Authors
Andrew D. Lin
Abstract
A length-$n$ binary $k$-deletion code is a set of binary strings such that if we delete any $k$ bits of a string, leaving a length-$(n-k)$ binary string, we can uniquely recover the codeword. In this paper, we consider $t$-list decodable deletion codes, where after $k$ bits of a codeword are deleted, we can identify a list of size at most $t$ such that the original codeword lies in the list. We prove a lower bound of $Ω_k(2^n t\log^{1/t}n/n^{k+k/t})$ on the optimal size of a $t$-list decodable $k$-deletion code, giving a $\sqrt{\log n}$ improvement over the previously best known bounds for $2$-list decodable $2$-deletion codes [GH21] and providing the first nontrivial lower bound when $t>2$ or $k>2$. Our bound holds for all $t\leq n^k$, showing that $t=Ω(\log n)-$list decodable deletion codes have optimal size $Θ_k(2^n t/n^k)$, asymptotically matching the known upper bound. We also prove upper bounds on the number of common subsequences and common supersequences of a given length for any two binary strings.