Explicit two-deletion codes with redundancy matching the existential bound

Venkatesan Guruswami, Johan Håstad

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…