Explicit Two-Deletion Codes With Redundancy Matching the Existential Bound

We give an explicit construction of length-n binary codes capable of correcting the deletion of two bits that have size 2(n)/n(4+o(1)). This matches up to lower order terms the existential result, based on an inefficient greedy choice of codewords, that guarantees such codes of size Omega(2(n)/n(4)). Our construction is based on augmenting the classic Varshamov-Tenengolts construction of single deletion codes with additional check equations. We also give an explicit construction of binary codes of size Omega(2(n)/n(3+o(1))) that can be list decoded from two deletions using lists of size two. Previously, even the existence of such codes was not clear.

Automated summary

The study provides a constructive method for correcting errors in binary codes after deleting two bits, and explicitly determines the size of the codes. The existence of such codes was previously unclear.