Efficient Low-Redundancy Codes for Correcting Multiple Deletions

We consider the problem of constructing 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 code from 1965 giving an asymptotically optimal construction with ~ 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^{Omega(1)}.

For any fixed k, we construct a binary code with c_k log n redundancy that is capable of efficiently recovering from k deletions (the coefficient c_k depends polynomially on k). When randomness (independent of the deletion pattern) is allowed at the encoder, we get codes with O(k log n) redundancy, matching the existential bound up to constant factors.

We also note that amongst linear codes capable of correcting k deletions, the (k+1)-fold repetition code is essentially the best possible.

Joint work with Joshua Brakensiek and Samuel Zbarsky (Carnegie Mellon).