Explicit Two-Deletion Codes With Redundancy Matching the Existential Bound
Venkatesan Guruswami, Johan Håstad
Abstract
We give an explicit construction of length- n binary codes capable of correcting the deletion of two bits that have size 2 <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</sup> /n <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">4+o(1)</sup> . This matches up to lower order terms the existential result, based on an inefficient greedy choice of codewords, that guarantees such codes of size Ω(2 <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</sup> /n <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">4</sup> ). 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 Ω(2 <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</sup> /n <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">3+o(1)</sup> ) that can be list decoded from two deletions using lists of size two. Previously, even the existence of such codes was not clear.