Venkatesan Guruswami: 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 O(k^2 log k log n) redundancy that is capable of efficiently recovering from k deletions, which comes close to the optimal, non-constructive Theta(k log n) bound.

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