Efficient Low-Redundancy Codes for Correcting Multiple Deletions

Joshua Brakensiek, Venkatesan Guruswami, Samuel Zbarsky

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 understoo…