Constructions and Lower Bounds for Deletion Codes

Abstract: A length n binary k-deletion code is a set of binary strings such that if we delete any k bits of a string, leaving a length-(n-k) binary string, we can uniquely recover the codeword. In this talk, we will first survey some known constructions for efficiently decodable deletion codes and lower bounds on the maximum size of a deletion code. Then, we present new results proving a lower bound on the size of t-list-decodable deletion codes, which is a generalization where instead of uniquely recovering a codeword, we are allowed to output a size-t list guaranteed to contain the codeword.