Source-linked AI summary
Efficient Low-Redundancy Codes for Correcting Multiple Deletions
Joshua Brakensiek, Venkatesan Guruswami, Samuel Zbarsky
TL;DR
The paper addresses the lack of efficient, explicit binary codes for correcting multiple deletions with low redundancy. It constructs such codes using pattern-based synchronization and hashing, achieving O(k^2 log k log N) redundancy with near-linear decoding for fixed k, and extends the approach to mixed insertions and deletions. The authors identify improving the redundancy further within their method as a central limitation.
Problem
Efficient explicit binary codes with redundancy near the Θ(k log N) existential bound were not known beyond the single-deletion case, even for two deletions.
Method
The construction creates pattern-rich strings using frequent patterns as implicit buffers and protects the resulting synchronization information with deletion-correcting hashes.
Results
For fixed k, the code has O(k^2 log k log N) redundancy and encoding and decoding time O_k(n(log n)^4), while also supporting up to k total insertions and deletions.
Takeaways & Limitations
The work provides the first efficient deterministic construction with subpolynomial-in-N redundancy for the two-deletion case and a near-linear-time extension to mixed edits.
Takeaways & Limitations
Within the proposed method, improving beyond n+O(k^2 log k log n) would require shorter distributed hashes or fewer patterns, but the authors identify obstacles to both routes.
Abstract
from arXiv · showhide
We consider the problem of constructing binary codes to recover from $k$-bit deletions with efficient encoding/decoding, for a fixed $k$. The single deletion case is well understood, with the Varshamov-Tenengolts-Levenshtein code from 1965 giving an asymptotically optimal construction with $\approx 2^n/n$ codewords of length $n$, i.e., at most $\log n$ bits of redundancy. However, even for the case of two deletions, there was no known explicit construction with redundancy less than $n^{Ω(1)}$. For any fixed $k$, we construct a binary code with $c_k \log n$ redundancy that can be decoded from $k$ deletions in $O_k(n \log^4 n)$ time. The coefficient $c_k$ can be taken to be $O(k^2 \log k)$, which is only quadratically worse than the optimal, non-constructive bound of $O(k)$. We also indicate how to modify this code to allow for a combination of up to $k$ insertions and deletions.
1 Introduction
For fixed k, the paper gives the first explicit binary deletion codes with logarithmic redundancy and near-linear decoding, extending efficiently to mixed insertions and deletions. The construction uses implicit frequent patterns as buffers, hashing, and protected auxiliary information to avoid the high redundancy of earlier approaches.
- Problem: Before this work, no explicit code had redundancy better than N even for correcting two deletions.The existential optimum is Θ(k log N) redundant bits, but efficient constructions approaching it were unknown beyond one deletion.
- Mixed edits: The code extends to arbitrary combinations of at most k insertions and deletions with near-linear-time correction.This extension goes beyond the combinatorial implication that deletion-correcting codes can correct mixed edits.
- Main result: O(k^2 log k log N) redundancy yields an explicit code correcting k deletions for every fixed k.The code has length N ≤ n+O(k^2 log k log n) and supports injective encoding.
- Main result: O_k(n(log n)^4) encoding and decoding time gives near-linear dependence on message length with fixed-parameter dependence on k.The decoding map recovers the message from every subsequence formed by deleting k bits.
- Construction: The construction replaces explicit buffers with frequent patterns that act as implicit buffers, then uses hashes and majority decoding across patterns.A pattern-rich transformation, per-pattern hashes, and protected auxiliary hashes support recovery despite corrupted pattern occurrences.
2 Preliminaries
The preliminaries define deletion confusability and introduce hashes that let a receiver reconstruct an n-bit string from a length-n−k subsequence. They develop an asymptotically short but inefficient hash and a longer, efficiently computable hash, alongside Reed–Solomon error correction.
- A subsequence is formed by deleting symbols, while σ_k(s) collects all length-n−k outputs of the k-bit deletion channel.
- Two strings are k-confusable exactly when they share a common length-n−k subsequence.
- The basic hash construction uses a color assigned to each string so the hash and any k-deletion subsequence identify the original string.The hash has length at most 2k log n + O(1), but its computation and decoding are exponential in n for fixed k.
- The efficient hash2 construction splits a string into O(n/log n) blocks, hashes each block, and concatenates the block hashes.Its hash length is approximately 2^k n log log n / log n, with computation and recovery time O_k(n^2(log n)^2k).
- A systematic Reed–Solomon map supplies a near-linear-time method for correcting k symbol errors in an appended redundancy block.The construction works over a power-of-two field with n+2k ≤ q = O(n).
3 Deletion-correcting hash for mixed strings
For strings containing every short binary pattern frequently, the paper builds a short deletion-correcting hash by splitting at pattern occurrences, hashing the resulting blocks, and protecting their hash values with Reed–Solomon redundancy. The resulting mixed-string decoder runs in O_k(n log^4 n) time.
- Pattern-rich strings: A k-mixed string contains every length-m pattern in every substring of length d.The paper defines p-split points as occurrences of a pattern p and chooses d on the order of k(log k)^2 log n.
- Hash construction: Theorem 5 provides a hash of length O(k^2 log k log n) that recovers any k-mixed string from an arbitrary k-deletion subsequence.Both hashing and recovery are computable in O_k(n log^4 n) time.
- Pattern-preserving deletions: A p-preserving deletion leaves the number of p occurrences unchanged and deletes no bit belonging to a p occurrence.This lets the decoder use the surviving pattern occurrences as block boundaries.
- Hash construction: The hash splits the mixed string at pattern occurrences, pads each block, applies hash2, and appends block lengths before Reed–Solomon encoding.The resulting 2^k protected values are serialized into equal-length binary blocks.
- Decoding: For a p-preserving subsequence, at most k block values change, so Reed–Solomon decoding restores the blocks and their lengths.The recovered block lengths remove padding, yielding the original string in O_k(n log^4 n) time.
- Decoding: The full decoder runs the pattern-specific procedure for every pattern and takes a bitwise majority of the resulting reconstructions.When deletions affect some patterns, other pattern hashes remain usable for recovery.
4 Encoding into Mixed Strings
The encoding procedure transforms any input string into a k-mixed string by XORing it with a carefully chosen repeating template. A deterministic obstruction-reduction algorithm finds the template in O_k(n log n) time.
- The map μ XORs an input string with repeated copies of a length-L template and truncates the result to length n.Applying μ with the same template twice recovers the input, and μ is computable in O(n) time.
- The resulting pattern-rich string can be decoded back to the original input using the same template because μ is self-inverting.
- Lemma 7 gives a deterministic template function T(s) whose transformed output μ(s,T(s)) is mixed for every input.T is computable in O(k^3(log k)^3 n log n) = O_k(n log n) time.
- A suitable template makes every length-2L substring contain every length-m pattern, thereby producing a k-mixed string.The construction chooses L so that 2L is at most floor(20000k(log k)^2 log n).
- The algorithm treats a missing pattern in a length-L block as an obstruction and chooses each template segment to reduce the number of potential obstructions.At each step it checks all 2^m segment choices and selects one achieving the expected reduction factor.
5 The Encoding/Decoding Scheme: Proof of Theorem 1
The final codeword stores a pattern-rich string together with the template and deletion-correcting hashes needed to recover both. Replacing naive repetition with shorter hashes yields O(k^2 log k log n) redundancy while preserving O_k(n log^4 n) encoding and decoding.
- Warm-up construction: The warm-up encoder transforms s into r = μ(s,t) and stores r, a repeated template, and a repeated mixed-string hash.This version has length n + O(k^3 log k log n), using (k+1)-fold repetition for protected auxiliary data.
- Decoding: The decoder first recovers the template and mixed-string hash, reconstructs r from its subsequence, and then computes s = μ(r,t).The mixed-string reconstruction uses Theorem 5 and runs in O_k(n log^4 n) time.
- Improved redundancy: The improved construction protects the template and mixed-string hash with shorter hashes instead of naive repetition.This reduces the encoding length to n + O(k^2 log k log n).
- Improved redundancy: The resulting codeword has O(k^2 log k log n) redundancy because hash2 applied to the O_k(log n)-length auxiliary strings produces only O_k(log n)-length hashes.These shorter hashes can be protected without changing the dominant redundancy term.
- Decoding: The improved decoder separates the received subsequence into the stored segments, corrects the repetition-protected hashes, and reconstructs the auxiliary strings before decoding the mixed string.The segment boundaries are known in advance, so each component can be recovered despite up to k deletions.
6 Efficient Algorithm for Correcting Insertions and Deletions
The deletion-correcting code can be modified to handle up to k insertions and deletions while preserving near-linear decoding and asymptotically similar redundancy.
- Main result: Levenshtein’s theorem supplies the combinatorial insertion/deletion correction property, but the paper additionally modifies the decoding algorithm.The authors note that the theorem alone does not automatically provide efficient recovery.
- Proof modifications: The underlying error-correcting code and Lemma 7 remain unchanged, while other lemmas are adapted to insertion/deletion errors.Lemma 3 handles sections containing both boundary deletions and internal insertions; Theorem 5 continues to use preserved patterns and hashes.
- Encoding and decoding: The construction replaces the (k + 1)-fold repetition code with a (3k + 1)-fold repetition code.This accommodates up to k missing bits on each side and k spurious insertions inside a section.
- Encoding and decoding: Majority voting recovers each repeated block in linear time, after which the hashes reconstruct t, Hmixed(r), r, and s in near-linear time.The modified lemmas preserve the hash-based recovery pipeline for insertion/deletion errors.
- Main result: The modified construction efficiently corrects any combination of up to k insertions and deletions.Its redundancy is O(k^2 log k log n), and decoding remains near-linear.
7 Concluding remarks
The paper presents a first-order asymptotically optimal efficient deletion code, while identifying limits on improving its length and open synchronization questions.
- Limitations: The code is first-order asymptotically optimal, with further improvement constrained by the hash information required across patterns.The authors argue that distributing hash information across patterns may be necessary, while an adversary can ruin k essentially independent patterns.
- Open problems: The approach leaves open deterministic one-way synchronization with poly(k log n) communication for arbitrary strings.The paper obtains such a protocol when the string x is mixed, but the arbitrary-string case remains open.
- Open problems: A possible multiple-deletion extension of the VT code using bounded-degree check coefficients remains unresolved.For two deletions, counterexamples exist for degree d ≤ 4, and no bounded-degree polynomial hash may work.